<p>Answer to your first question: Seems unlikely.</p>

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

<p>Given a circuit $C$ that outputs a bit, define the <em>decompression of C</em> 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)$. </p>

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

<p>Now consider the language </p>

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

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

<p>$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)$.</p>

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

<p>Your second question is wide open (and open-ended).</p>

CC BY-SA 2.5
2010-10-06T21:48:38.583Z
Why do you need to take some complete problem?
Yuval Filmus
CC BY-SA 2.5
2010-10-06T22:09:24.857Z
Thought it made the argument easier to follow.
Ryan Williams
CC BY-SA 2.5
2010-10-07T04:21:42.137Z
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
CC BY-SA 2.5
2010-10-06T21:32:05.787Z
2010-10-06T21:32:05.787Z
Ryan Williams
<p>To the question of Kaveh "Can non-uniformity help us in computing natural uniform problems?" </p>

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

<p>References:</p>

<ul>
<li>Friedhelm Meyer auf der Heide, "<a href="http://doi.acm.org/10.1145/828.322450" rel="nofollow noreferrer">A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem</a>", 1984</li>
</ul>

CC BY-SA 3.0
2011-07-06T22:03:42.250Z
Thank you. Interesting result, but looking at [A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem](http://www2.cs.uni-paderborn.de/cs/ag-madh/vorl/Perlen/Korzeniowski.ps.gz), 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
CC BY-SA 3.0
2011-07-06T22:34:06.093Z
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
CC BY-SA 3.0
2011-07-07T09:44:22.747Z
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
CC BY-SA 3.0
2011-07-07T18:41:06.777Z
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
CC BY-SA 3.0
2011-07-07T19:27:06.793Z
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
CC BY-SA 3.0
2011-07-08T01:32:11.353Z
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
CC BY-SA 3.0
2011-07-18T15:03:18.443Z
@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
CC BY-SA 3.0
2011-07-06T19:03:46.300Z
2017-04-03T17:01:43.187Z
2017-04-03T17:01:43.187Z
Stasys
<p>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$.</p>

CC BY-SA 3.0
2013-01-30T01:37:47.573Z
Essentially the same transformation is used in [Book 1974](http://dx.doi.org/10.1016/S0019-9958%2874%2990473-2) to show that E≠NE if and only if NP∖P contains a tally language.
Tsuyoshi Ito
CC BY-SA 3.0
2016-07-13T11:49:30.023Z
Just to be sure: do I understand correctly that $|x|$ is the length of $x$ written in unary?
Vincent
CC BY-SA 3.0
2016-07-13T13:14:54.840Z
@Vincent Here $x$ is a string rather than an integer, and $|x|$ is its length.
Yuval Filmus
CC BY-SA 3.0
2016-07-13T13:20:22.160Z
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$?
Vincent
CC BY-SA 3.0
2016-07-13T13:23:16.153Z
@Vincent It's encoded in binary (more accurately, take the $|x|$'th string in non-decreasing order of length).
Yuval Filmus
CC BY-SA 2.5
2010-10-07T08:40:18.877Z
Nice answer Yuval!
Dai Le
CC BY-SA 2.5
2010-10-06T21:47:52.813Z
2010-10-06T21:47:52.813Z
Yuval Filmus
<p>I thought I would share this question as it might be interesting for other users here.</p>

<p>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?</p>

<blockquote>
  <p>Is $AC^0/poly \cap NP$ contained in $P$?</p>
</blockquote>

<p>Note: A <a href="https://cstheory.stackexchange.com/users/40/yuval-filmus">friend</a> has already partially answered my question offline, I will add his answer if he doesn't add it himself. </p>

<p>The question is my second attempt to formalize the following informal question: </p>

<blockquote>
  <p>Can non-uniformity help us in computing natural uniform problems?</p>
</blockquote>

<hr>

<p>Related:</p>

<ul>
<li><a href="https://cstheory.stackexchange.com/questions/1662/is-there-a-candidate-for-a-natural-problem-in-p-poly-p">Is there a candidate for a natural problem in $P/poly−P$?</a></li>
</ul>

CC BY-SA 2.5
2010-10-06T22:28:00.890Z
@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
CC BY-SA 2.5
2010-10-07T04:09:57.417Z
@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
CC BY-SA 2.5
2010-10-07T04:19:24.497Z
@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
CC BY-SA 2.5
2010-10-07T04:30:03.587Z
@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
CC BY-SA 2.5
2010-10-07T04:57:52.860Z
@Robin: Thank you, that seems very interesting, I will check it, do you know a good reference on $YP$ (other than Scott's [post](http://scottaaronson.blogspot.com/2006/04/what-is-name-of-this-post.html))?
Kaveh
CC BY-SA 2.5
2010-10-07T14:17:43.943Z
@Kaveh: Nope. I heard about it during Scott's talk.
Robin Kothari
CC BY-SA 2.5
2010-10-07T16:09:10.327Z
@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
<cc.complexity-theory><circuit-complexity><uniformity>
Is $AC^0/poly \cap NP$ contained in $P$?
Kaveh
# Is $AC^0/poly \cap NP$ contained in $P$?

(Asked by: username_0 on 2010-10-06)

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](https://cstheory.stackexchange.com/users/40/yuval-filmus) 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:

* [Is there a candidate for a natural problem in $P/poly−P$?](https://cstheory.stackexchange.com/questions/1662/is-there-a-candidate-for-a-natural-problem-in-p-poly-p)

**Tags:** cc.complexity-theory, circuit-complexity, uniformity
> **Comments:**
> **username_1**: @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?)  
> **username_0**: @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$.  
> **username_0**: @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.  
> **username_1**: @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.  
> **username_0**: @Robin: Thank you, that seems very interesting, I will check it, do you know a good reference on $YP$ (other than Scott's [post](http://scottaaronson.blogspot.com/2006/04/what-is-name-of-this-post.html))?  
> **username_1**: @Kaveh: Nope. I heard about it during Scott's talk.  
> **username_2**: @Kaveh: The class YP ("Yoda Polynomial-Time") is more formally defined in Scott's paper "The Learnability of Quantum States" [quant-ph/0608142]  

---

## 3 answers

### Answer by username_4 on 2010-10-06. Score: 33 | Accepted answer

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

> **Comments:**
> **username_8**: Nice answer Yuval!  
> **username_6**: Essentially the same transformation is used in [Book 1974](http://dx.doi.org/10.1016/S0019-9958%2874%2990473-2) to show that E≠NE if and only if NP∖P contains a tally language.  
> **username_7**: Just to be sure: do I understand correctly that $|x|$ is the length of $x$ written in unary?  
> **username_4**: @Vincent Here $x$ is a string rather than an integer, and $|x|$ is its length.  
> **username_7**: 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$?  
> **username_4**: @Vincent It's encoded in binary (more accurately, take the $|x|$'th string in non-decreasing order of length).  

---

### Answer by username_3 on 2010-10-06. Score: 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).

> **Comments:**
> **username_4**: Why do you need to take some complete problem?  
> **username_3**: Thought it made the argument easier to follow.  
> **username_0**: 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.  

---

### Answer by username_5 on 2011-07-06. Score: 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:

* Friedhelm Meyer auf der Heide, "[A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem](http://doi.acm.org/10.1145/828.322450)", 1984

> **Comments:**
> **username_0**: Thank you. Interesting result, but looking at [A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem](http://www2.cs.uni-paderborn.de/cs/ag-madh/vorl/Perlen/Korzeniowski.ps.gz), 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).  
> **username_0**: 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.  
> **username_5**: 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* :-)  
> **username_0**: 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).  
> **username_5**: 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.  
> **username_0**: 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.  
> **username_5**: @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).  

---

