34

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$?

Note: A friend has already partially answered my question offline, I will add his answer if he doesn't add it himself.

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

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

Related:

Community
  • 1
Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • @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 06 '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 07 '10 at 04:09
  • 1
    @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 07 '10 at 04:19
  • 2
    @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 07 '10 at 04:30
  • @Robin: Thank you, that seems very interesting, I will check it, do you know a good reference on $YP$ (other than Scott's post)? – Kaveh Oct 07 '10 at 04:57
  • @Kaveh: Nope. I heard about it during Scott's talk. – Robin Kothari Oct 07 '10 at 14:17
  • 2
    @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 07 '10 at 16:09

3 Answers3

33

Answer to your first question: Seems unlikely.

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).

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
32

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$.

Yuval Filmus
  • 14,445
  • 1
  • 48
  • 92
11

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 some 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 here is important: for every $n$ we may have entirely different algorithm (decision tree).

References:

Dylan McKay
  • 548
  • 4
  • 15
Stasys
  • 6,765
  • 29
  • 54
  • 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 06 '11 at 22:03
  • 1
    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 06 '11 at 22:34
  • 1
    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 07 '11 at 09:44
  • Yes, I am interested in natural candidate. :) But can't we just use a top OR gate (with a large fan-in) to combine the results of each candidate solution? Checking each candidate solution is polytime, so this should give a polynomial depth circuit. I.e. $\mathsf{NP}$ is contained in polynomial depth circuits (of this restricted form, i.e. a large OR of $\mathsf{P}/\text{poly}$ circuits). – Kaveh Jul 07 '11 at 18:41
  • 1
    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 07 '11 at 19:27
  • Yes, the circuit I described has a big OR on top (and hence exponential size) but it is not really a non-deterministic circuit, so I think it counts as a deterministic circuit (and I think is similar to the one in the paper). If it was non-deterministic, I wouldn't need the big OR on top and could solve it with a polynomial size circuit. – Kaveh Jul 08 '11 at 01:32
  • 4
    @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