Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 25 down vote accepted

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

share|cite|improve this answer
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 Dec 5 '10 at 22:33

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.

share|cite|improve this answer
A nice and superior answer as always. :) – Kaveh Dec 5 '10 at 18:50

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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