Fix a constant k. In 1982 Ravi Kannan showed that some Σ _{2}^{p}∩Π_{2}^{p}language must not have n^{k}-size (nonuniform) circuits. Here is a proof sketch: A simple counting argument shows there is a function that depends only on the first 5k log n inputs that is not equivalent to a n^{k}-size circuit. Just by writing out the quantifiers in Σ_{4}^{p}you can compute the lexicographically first such function. Now we have two cases:- If SAT does not have polynomial-size circuits then SAT then
Σ
_{2}^{p}∩Π_{2}^{p}which contains SAT does not have n^{k}-size circuits. - If SAT
has polynomial-size circuits then
Σ
_{4}^{p}=Σ_{2}^{p}∩Π_{2}^{p}(Karp-Lipton) and thus Σ_{2}^{p}∩Π_{2}^{p}does not have n^{k}-size circuits.

_{2}^{p}∩Π_{2}^{p}language without quadratic-size circuits is open. With better known collapses we can improve the result from Σ_{2}^{p}∩Π_{2}^{p}to S_{2}^{p}.Vinod Variyam recently observed that the class PP which is not known to contain S

_{2}^{p}also cannot have n^{k}-size circuits. Here is his proof: If PP has n^{k}-size circuits then PP is in P/poly which implies the polynomial-time hierarchy and in particular Σ_{2}^{p}is in MA which is in PP which has n^{k}-size circuits contradicting Kannan.Read Variyam's paper for details and references.

--

Posted by Lance to My Computational Complexity Web Log at 8/4/2004 05:45:06 AM- If SAT does not have polynomial-size circuits then SAT then
Σ