

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

I have a basic question about circuit complexity. Apparently no example of a language that requires super-polynomial circuits to decide is known. (This is despite the fact that an easy counting argument shows that there must be many such languages.)

On the hand it is known that P/poly does not contain all of EXPSPACE. I was wondering why did this not imply that any EXPSPACE-complete problem must have super-polynomial circuit complexity. I figured it was because I might not be able to reduce any problem to a complete problem using polynomial-sized circuits. Is that correct?

On the other hand, I should be able to reduce any problem in NP to SAT using polynomial-sized circuits. So am I correct if I claim that the existence of polynomial sized circuits for SAT implies that P/poly contains NP?

share|cite|improve this question
You might get a better answer at . – Qiaochu Yuan May 2 '11 at 21:51
@Qiaochu: He will get laughed at in cstheory. – Yuval Filmus May 3 '11 at 0:17
@Qiaochu: to CS is like mathoverflow for math. I believe (for better or worse) is the best platform for non-research level questions on CS theory. – Michael Chen May 3 '11 at 2:29
up vote 7 down vote accepted

The proof that shows that P/poly doesn't contain all of EXPSPACE, using diagonalization (contained for example in Kannan's classic 1982 paper), actually produces some concrete language in EXPSPACE which is not in P/poly. So in this sense there are concrete languages requiring super-polynomial circuits. See also this paper and that paper.

Now consider a language M which is EXPSPACE-complete (e.g. equivalence of regexps with exponentiation). Suppose it had polynomial-size circuits. Any language L in EXPSPACE is reducible to M using a polytime reduction (that's the definition of EXPSPACE-completeness). This implies that L has polynomial-size circuits. So EXPSPACE is contained in P/poly. This contradicts the fact you've mentioned.

It becomes harder to obtain super-polynomial bound if we want the language to be "easy" - the extreme example being some language in NP. If SAT has polynomial-size circuits then, as you mention, all of NP is contained in P/poly. The front line is EXP - no one knows how to prove that EXP is not contained in P/poly.

share|cite|improve this answer

Your Answer


