Computational Complexity

Wednesday, August 04, 2004

 
Small Circuits

Posted by Lance

Fix a constant k. In 1982 Ravi Kannan showed that some Σ₂^p∩Π₂^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 Σ₄^p 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 Σ₂^p∩Π₂^p which contains SAT does not have n^k-size circuits.
2. If SAT has polynomial-size circuits then Σ₄^p=Σ₂^p∩Π₂^p (Karp-Lipton) and thus Σ₂^p∩Π₂^p does not have n^k-size circuits.

This is a wonderful example of a non-constructive proof and giving an explicit Σ₂^p∩Π₂^p language without quadratic-size circuits is open. With better known collapses we can improve the result from Σ₂^p∩Π₂^p to S₂^p.

Vinod Variyam recently observed that the class PP which is not known to contain S₂^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 Σ₂^p is in MA which is in PP which has n^k-size circuits contradicting Kannan.

Read Variyam's paper for details and references.

5:45 AM #

Comment Feeds: This Post All