## [My Computational Complexity Web Log] Small Circuits

Expand Messages
• 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
Message 1 of 1 , Aug 4, 2004
• 0 Attachment
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:
1. If SAT does not have polynomial-size circuits then SAT then Σ2p∩Π2p which contains SAT does not have nk-size circuits.
2. If SAT has polynomial-size circuits then Σ4p2p∩Π2p (Karp-Lipton) and thus Σ2p∩Π2p does not have nk-size circuits.
This is a wonderful example of a non-constructive proof and giving an explicit Σ2p∩Π2p language without quadratic-size circuits is open. With better known collapses we can improve the result from Σ2p∩Π2p to S2p.

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.

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

Your message has been successfully submitted and would be delivered to recipients shortly.