Wednesday, August 04, 2004

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:
  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.

No comments:

Post a Comment