# Is $AC^0/poly \cap NP$ contained in $P$?

I thought I would share this question as it might be interesting for other users here.

Assume that a function which is in a uniform class (like $NP$) is also in a small nonuniform class (like $AC^0/poly$, i.e. nonuniform $AC^0$), does this imply that the function is contained in a smaller uniform class (like $P$)? If the answer to this question is positive, what is the smallest uniform complexity class that contains $NP \cap AC^0/poly$? If negative, can we find an interesting natural counterexample?

Is $AC^0/poly \cap NP$ contained in $P$?

The question is my second attempt to formalize the following informal question:

Can non-uniformity help us in computing natural uniform problems?

Related:

-
@Kaveh: Maybe an interesting question would be to ask for a natural problem in P/poly and NP, but not in P. (Or maybe this is too easy?) –  Robin Kothari Oct 6 '10 at 22:28
@Robin: that seems interesting, but I am not sure that it would be easier to find a natural problem in $NP \cap P/poly - P$. –  Kaveh Oct 7 '10 at 4:09
@all: I need to think a little bit more about this question and the answers. It seems very natural question. But I feel uneasy about the answers: first, we can weaken the assumption by replacing $NEXP \neq EXP$ with $NTime(f) \neq DTime(f)$ where $f$ is a very fast growing function; second, the counterexample is not just in $AC^0/poly$ but has circuits of size 1 as the function is constant on all inputs of size $n$ for all $n$! These two reasons might be saying that this is not the right question to ask. –  Kaveh Oct 7 '10 at 4:19
@Kaveh: Perhaps you might want to look at the class YP, defined by Scott Aaronson. It is like P/poly, but the "advice" is not trusted. In other words, it is like NP intersect coNP, but the witness can only depend on the input length. YP is in P/poly, and is a uniform class. Perhaps a problem in YP but not in P is an example of the problem you're looking for. It would be natural, uniform, not in P, in P/poly, and possibly non-trivial since the advice has to be verified by the circuit. –  Robin Kothari Oct 7 '10 at 4:30
@Kaveh: The class YP ("Yoda Polynomial-Time") is more formally defined in Scott's paper "The Learnability of Quantum States" [quant-ph/0608142] –  Alessandro Cosentino Oct 7 '10 at 16:09

Here's a simplification of Ryan's answer. Suppose that $\Lambda \in NE \setminus E$. Define the language $L = \{x : |x| \in \Lambda\}$. The assumption $\Lambda \in NE \setminus E$ translates to $L \in NP \setminus P$. Also, trivially $L \in AC^0/poly$.

-
Thank you for posting your answer. –  Kaveh Oct 7 '10 at 4:54
Nice answer Yuval! –  Dai Le Oct 7 '10 at 8:40
Essentially the same transformation is used in Book 1974 to show that E≠NE if and only if NP∖P contains a tally language. –  Tsuyoshi Ito Jan 30 '13 at 1:37

Theorem: If $NP \cap AC^0/poly \subseteq P$ then $NEXP = EXP$.

Given a circuit $C$ that outputs a bit, define the decompression of C to be the bit string obtained by evaluating $C$ on all possible inputs. That is, the decompression is $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$.

Define the Succinct 3SAT problem as: given a circuit $C$ of size $n$, does its decompression encode a satisfiable Boolean formula? Succinct 3SAT is well-known to be $NEXP$ complete.

Now consider the language

$L =${$1^n |$the integer $n$ written in binary is a yes-instance of Succinct 3SAT}.

$L$ is clearly in $AC^0/poly$, since you can just hardcode whether $1^n$ is in $L$, for each $n$.

$L$ is also in $NP$: the integer $n$ written in binary has length about $\log n$, so the decompression of this circuit has length no more than $O(n)$. Hence the satisfying assignment has length at most $O(n)$.

But by the same observations, if $L \in P$, then $NEXP=EXP$, because it means that you have an $O(n^c)$ time algorithm for deciding every instance of Succinct 3SAT of length $\log n$.

Your second question is wide open (and open-ended).

-
Why do you need to take some complete problem? –  Yuval Filmus Oct 6 '10 at 21:48
Thought it made the argument easier to follow. –  Ryan Williams Oct 6 '10 at 22:09
Thank you Ryan for your nice answer and the explanation. I guess you would not mind if I accept Yuval's answer although you were the first person to post. –  Kaveh Oct 7 '10 at 4:21

To the question of Kaveh "Can non-uniformity help us in computing natural uniform problems?"

I think the answer is "yes", sometimes. Consider, for example, the Subset-Sum problem: given a sequence of $n$ positive real numbers, decide whether sum subset of them sums up to $1$. This is an NP-hard problem even if restricted to positive integers (Knapsack). But Friedhelm Meyer auf der Heide (1984) has shown that, for any $n$, the problem can be solved by a linear decision tree of depth smaller than $n^5$. In such a tree tests are of the form: is a linear combination of input variables larger than some threshold. Non-uniformity is here important: for every $n$ we may have entirely different algorithm (decision tree).

References:

-
Thank you. Interesting result, but looking at A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, it seems a little bit of cheating to me. The size of the nonuniform program is exponential, only the depth is polynomial, it is like considering the whole computation tree of an NP algorithm on inputs of size $n$ (it is like polynomial depth exponential size circuits). –  Kaveh Jul 6 '11 at 22:03
By a similar argument, we can say that any problem is solvable in constant time $2$, because the table of answers can be expressed by a CNF. I like Ryan and Yuval's construction more because it shows that although the problem is complicated in the uniform setting, for each input size it is very easy to solve. –  Kaveh Jul 6 '11 at 22:34
Kaveh, you are right: here we are interested in time (=depth), not in space (=log of network size). But note that a trivial algorithm for Subset-Sum would require time (depth) $2^n$ to test all subsets of a given input string. Also, I thought your ask about natural candidates, not just for separation :-) –  Stasys Jul 7 '11 at 9:44
Of course, the Subset-Sum problem has a trivial non-deterministic algorithm: just guess a subset summing up to $1$. But we speak about deterministic algorithms. And that of Mayer auf der Heide is a deterministic one. B.t.w. I am also not very excited about his result. Had he shown this for the size (not for just for depth = time), we would already have $NP\subseteq P/poly$. Still, this is one of THE results. –  Stasys Jul 7 '11 at 19:27
@Kaveh: But NP itself is a big OR of P. The "time version" of P vs. NP is: can we replace this big OR by a deterministic algebraic decision tree of polynomial depth (with P on the leaves)? Recall that the trivial depth for Subset-Sum is 2^n (not n). Dopkin and Lipton (1978) showed that depth n^2/2 is necessary, and it was widely believed that this can be improved to n^k for any k. Mayer auf der Heide refuted this belief: k=5 is enough. Thus, non-uniformity CAN help, if we are interested in depth (time). –  Stasys Jul 18 '11 at 15:03