[My Computational Complexity Web Log] Small Circuits
Fix a constant k. In 1982 Ravi Kannan showed that some Σ2p∩Π2p language must not have nk-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 nk-size circuit. Just by writing out the quantifiers in Σ4p you can compute the lexicographically first such function. Now we have two cases:
- If SAT does not have polynomial-size circuits then SAT then Σ2p∩Π2p which contains SAT does not have nk-size circuits.
- If SAT has polynomial-size circuits then Σ4p=Σ2p∩Π2p (Karp-Lipton) and thus Σ2p∩Π2p does not have nk-size circuits.
Vinod Variyam recently observed that the class PP which is not known to contain S2p also cannot have nk-size circuits. Here is his proof: If PP has nk-size circuits then PP is in P/poly which implies the polynomial-time hierarchy and in particular Σ2p is in MA which is in PP which has nk-size circuits contradicting Kannan.