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.