35
$\begingroup$

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:

Improve this question
$\endgroup$
7
  • $\begingroup$ @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?) $\endgroup$
    – Robin Kothari
    Commented Oct 6, 2010 at 22:28
  • $\begingroup$ @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$. $\endgroup$
    – Kaveh
    Commented Oct 7, 2010 at 4:09
  • 1
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Commented Oct 7, 2010 at 4:19
  • 2
    $\begingroup$ @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. $\endgroup$
    – Robin Kothari
    Commented Oct 7, 2010 at 4:30
  • 2
    $\begingroup$ @Kaveh: The class YP ("Yoda Polynomial-Time") is more formally defined in Scott's paper "The Learnability of Quantum States" [quant-ph/0608142] $\endgroup$
    – Alessandro Cosentino
    Commented Oct 7, 2010 at 16:09

3 Answers 3

Reset to default
33
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Nice answer Yuval! $\endgroup$
    – Dai Le
    Commented Oct 7, 2010 at 8:40
  • 1
    $\begingroup$ Essentially the same transformation is used in Book 1974 to show that E≠NE if and only if NP∖P contains a tally language. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 30, 2013 at 1:37
  • $\begingroup$ Just to be sure: do I understand correctly that $|x|$ is the length of $x$ written in unary? $\endgroup$
    – Vincent
    Commented Jul 13, 2016 at 11:49
  • $\begingroup$ @Vincent Here $x$ is a string rather than an integer, and $|x|$ is its length. $\endgroup$
    – Yuval Filmus
    Commented Jul 13, 2016 at 13:14
  • $\begingroup$ yes that is what confuses me. If $|x|$ is the length of some string, then $|x|$ is an integer, so how can it be an element of $\Lambda$? $\endgroup$
    – Vincent
    Commented Jul 13, 2016 at 13:20
33
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Why do you need to take some complete problem? $\endgroup$
    – Yuval Filmus
    Commented Oct 6, 2010 at 21:48
  • $\begingroup$ Thought it made the argument easier to follow. $\endgroup$
    – Ryan Williams
    Commented Oct 6, 2010 at 22:09
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Oct 7, 2010 at 4:21
11
$\begingroup$

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:

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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). $\endgroup$
    – Kaveh
    Commented Jul 6, 2011 at 22:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Jul 6, 2011 at 22:34
  • 1
    $\begingroup$ 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 :-) $\endgroup$
    – Stasys
    Commented Jul 7, 2011 at 9:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Stasys
    Commented Jul 7, 2011 at 19:27
  • 4
    $\begingroup$ @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). $\endgroup$
    – Stasys
    Commented Jul 18, 2011 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.