<p>The strongest result I am aware of is that for all k, there is a problem in $S_2^P$ that requires circuits of size $\Omega(n^k)$.</p>

<p>$S_2^P$ is a class contained in $ZPP^{NP}$, which is itself contained in $\Sigma_2^P \cap \Pi_2^P$. (The <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#s2p">complexity zoo</a> has more information about this class.)</p>

<p>The result follows from the strongest version of the Karp-Lipton theorem due to <a href="http://dx.doi.org/10.1016/j.jcss.2003.07.015">Cai</a>. </p>

<p>A quick proof of how this follows from the K-L theorem: First, if SAT requires super-polynomial size circuits, we are done, since we've exhibited a problem in $S_2^P$ that needs super-polynomial size circuits. If SAT has polynomial size circuits, then by the strongest version of the Karp-Lipton theorem, PH collapses to $S_2^P$. We know PH contains problems such problems (by Kannan's result), and thus $S_2^P$ contains such a problem.</p>

CC BY-SA 2.5
2010-12-05T18:50:00.377Z
A nice and superior answer as always. :)
Kaveh
CC BY-SA 2.5
2010-12-05T18:39:57.197Z
2010-12-05T18:39:57.197Z
Robin Kothari
<p>For general circuits, we know that there are problems in $\Sigma^p_2 \cap \Pi^p_2$ that require circuits of size $\Omega(n^k)$, this is due to Ravi Kannan (1981) and is based on his result that $PH$ contains such problems.</p>

<p>I think the best lowerbounds for $NP$ are still around $5n$.</p>

<p>See Arora and Barak's book, page 297. Richard J. Lipton had <a href="http://rjlipton.wordpress.com/2010/03/31/a-problem-with-proving-problems-are-hard/">a post</a> on <a href="http://rjlipton.wordpress.com/">his blog</a> about these results, also see <a href="http://rjlipton.wordpress.com/2010/09/02/old-ideas-and-lower-bounds-on-sat/">this one</a>. </p>

CC BY-SA 2.5
2010-12-05T18:08:22.363Z
2010-12-05T18:33:11.663Z
2010-12-05T18:33:11.663Z
Kaveh
<p>To refine the $\mathrm{S}_2\mathrm{P}$ answer, for every $k≥1$ and $c$, either<br/>
* The 3-SAT search problem does not have $\tilde{O}(n^k)$ circuits, or<br/>
* Some problem in <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:O#o2p" rel="nofollow noreferrer">$\mathrm{O}_2\mathrm{P}$</a> with time (and witness size) restricted to $\tilde{O}(n^{k^2})$ does not have i.o.-$O(n^k (\log n)^c)$ circuits (i.o. means infinitely often).</p>

<p>If in place of 3-SAT search problem, we used the decision problem, $\mathrm{O}^2\mathrm{P}$ time $\tilde{O}(n^{k^2+k})$ suffices, and if we used the decision problem for bit $i$ in the lexicographically minimal assignment for 3-SAT, $\tilde{O}(n^{\min(k^2+k,k^3)})$ suffices.</p>

<p>One decision problem not computable with i.o.-$O(n^k (\log n)^c)$ circuits is the least number $N$ (queried using its binary digits) that is not the truth table of a circuit with $n^k ⌊(\log n)^{c+1}⌋$ gates.  If NP is in P/poly, the problem has an irrefutable oblivious witness consisting of the following:<br/>
(1) $N$<br/>
(2) a circuit that given $N' &lt; N$, shows that $N'$ has a sufficiently small circuit.<br/>
(3) (only used for the $\tilde{O}(n^{k^3})$ bound) a verifier that enables us to run the opponent's circuit for (2) only $O(1)$ times (getting 1 bit per run).</p>

<p>On a separate note, for every $k$, there are decision problems in (MA ∩ coMA)/1 that do not have $O(n^k)$ circuits.  '/1' means that the machine gets one bit of advice that depends only on the input size. Also, the string Merlin sends can be chosen to depend only on the input size (with this restriction, MA is a subset of $\mathrm{O}_2\mathrm{P}$), and the advice complexity $Σ_2^P$.  The proof (Santhanam 2007) generalizes IP=PSPACE and PSPACE⊂P/poly ⇒ PSPACE=MA by using a certain well-behaved PSPACE-complete problem and padding the inputs to get minimum circuit sizes that are infinitely often between $n^{k+1}$ and $n^{k+2}$, using advice to detect enough examples of such $n$, and for these $n$, solving the padded problem by having Merlin produce such a circuit.</p>

CC BY-SA 3.0
2017-10-04T02:22:16.087Z
2017-10-04T02:22:16.087Z
Dmytro Taranovsky
<p>I believe that the smallest such classes known are $S_2P$ (Cai, 2001), $PP$ (Vinodchandran, 2005), and $(MA \cap coMA)/1$ (Santhanam, 2007).  All of these are indeed known to not be in $SIZE(n^k)$ for each constant $k$.</p>

CC BY-SA 2.5
2010-12-05T22:33:33.450Z
Thanks all for the answers.  I'm accepting Ryan's as it has the biggest variety of results, but thanks Robin and Kaveh for the detailed explanations.
matt hastings
CC BY-SA 2.5
2010-12-05T19:07:55.990Z
2010-12-05T19:07:55.990Z
Ryan O'Donnell
<p>Apologies for asking a question that must surely be in a lot of standard references.  I'm curious about exactly the question in the title, in particular I am thinking of Boolean circuits, no depth bound.  I put "smallest" in quotes to allow for the possibility there are multiple different classes, not known to include each other, for which a superlinear bound is known.</p>

<cc.complexity-theory><circuit-complexity>
What's the "smallest" complexity class for which a superlinear circuit bound is known?
matt hastings
# What's the "smallest" complexity class for which a superlinear circuit bound is known?

(Asked by: username_0 on 2010-12-05)

Apologies for asking a question that must surely be in a lot of standard references. I'm curious about exactly the question in the title, in particular I am thinking of Boolean circuits, no depth bound. I put "smallest" in quotes to allow for the possibility there are multiple different classes, not known to include each other, for which a superlinear bound is known.

**Tags:** cc.complexity-theory, circuit-complexity

---

## 4 answers

### Answer by username_4 on 2010-12-05. Score: 26 | Accepted answer

I believe that the smallest such classes known are $S\_2P$ (Cai, 2001), $PP$ (Vinodchandran, 2005), and $(MA \cap coMA)/1$ (Santhanam, 2007). All of these are indeed known to not be in $SIZE(n^k)$ for each constant $k$.

> **Comments:**
> **username_0**: Thanks all for the answers.  I'm accepting Ryan's as it has the biggest variety of results, but thanks Robin and Kaveh for the detailed explanations.  

---

### Answer by username_1 on 2010-12-05. Score: 20

The strongest result I am aware of is that for all k, there is a problem in $S\_2^P$ that requires circuits of size $\Omega(n^k)$.

$S\_2^P$ is a class contained in $ZPP^{NP}$, which is itself contained in $\Sigma\_2^P \cap \Pi\_2^P$. (The [complexity zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#s2p) has more information about this class.)

The result follows from the strongest version of the Karp-Lipton theorem due to [Cai](http://dx.doi.org/10.1016/j.jcss.2003.07.015).

A quick proof of how this follows from the K-L theorem: First, if SAT requires super-polynomial size circuits, we are done, since we've exhibited a problem in $S\_2^P$ that needs super-polynomial size circuits. If SAT has polynomial size circuits, then by the strongest version of the Karp-Lipton theorem, PH collapses to $S\_2^P$. We know PH contains problems such problems (by Kannan's result), and thus $S\_2^P$ contains such a problem.

> **Comments:**
> **username_2**: A nice and superior answer as always. :)  

---

### Answer by username_2 on 2010-12-05. Score: 13

For general circuits, we know that there are problems in $\Sigma^p\_2 \cap \Pi^p\_2$ that require circuits of size $\Omega(n^k)$, this is due to Ravi Kannan (1981) and is based on his result that $PH$ contains such problems.

I think the best lowerbounds for $NP$ are still around $5n$.

See Arora and Barak's book, page 297. Richard J. Lipton had [a post](http://rjlipton.wordpress.com/2010/03/31/a-problem-with-proving-problems-are-hard/) on [his blog](http://rjlipton.wordpress.com/) about these results, also see [this one](http://rjlipton.wordpress.com/2010/09/02/old-ideas-and-lower-bounds-on-sat/).


---

### Answer by username_3 on 2017-10-04. Score: 1

To refine the $\mathrm{S}\_2\mathrm{P}$ answer, for every $k≥1$ and $c$, either  
\* The 3-SAT search problem does not have $\tilde{O}(n^k)$ circuits, or  
\* Some problem in [$\mathrm{O}\_2\mathrm{P}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:O#o2p) with time (and witness size) restricted to $\tilde{O}(n^{k^2})$ does not have i.o.-$O(n^k (\log n)^c)$ circuits (i.o. means infinitely often).

If in place of 3-SAT search problem, we used the decision problem, $\mathrm{O}^2\mathrm{P}$ time $\tilde{O}(n^{k^2+k})$ suffices, and if we used the decision problem for bit $i$ in the lexicographically minimal assignment for 3-SAT, $\tilde{O}(n^{\min(k^2+k,k^3)})$ suffices.

One decision problem not computable with i.o.-$O(n^k (\log n)^c)$ circuits is the least number $N$ (queried using its binary digits) that is not the truth table of a circuit with $n^k ⌊(\log n)^{c+1}⌋$ gates. If NP is in P/poly, the problem has an irrefutable oblivious witness consisting of the following:  
(1) $N$  
(2) a circuit that given $N' < N$, shows that $N'$ has a sufficiently small circuit.  
(3) (only used for the $\tilde{O}(n^{k^3})$ bound) a verifier that enables us to run the opponent's circuit for (2) only $O(1)$ times (getting 1 bit per run).

On a separate note, for every $k$, there are decision problems in (MA ∩ coMA)/1 that do not have $O(n^k)$ circuits. '/1' means that the machine gets one bit of advice that depends only on the input size. Also, the string Merlin sends can be chosen to depend only on the input size (with this restriction, MA is a subset of $\mathrm{O}\_2\mathrm{P}$), and the advice complexity $Σ\_2^P$. The proof (Santhanam 2007) generalizes IP=PSPACE and PSPACE⊂P/poly ⇒ PSPACE=MA by using a certain well-behaved PSPACE-complete problem and padding the inputs to get minimum circuit sizes that are infinitely often between $n^{k+1}$ and $n^{k+2}$, using advice to detect enough examples of such $n$, and for these $n$, solving the padded problem by having Merlin produce such a circuit.


---

