What's the "smallest" complexity class for which a superlinear circuit bound is known?

Question

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.

Answer 1

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

Answer 2

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 has more information about this class.)

The result follows from the strongest version of the Karp-Lipton theorem due to Cai.

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.

Answer 3

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 on his blog about these results, also see this one.

Answer 4

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