Sunday, November 19, 2006

Favorite Theorems: Nonuniform Complexity

October Edition

The class P/poly is the set of languages that have polynomial-size circuit families, i.e., L is in P/poly if there is a k, a sequence of Boolean circuits C0, C1, … where Cn has n inputs and at most n^k gates, such that and all x=x1x2…xn,

x is in L iff Cn(x1,x2,…,xn)=1.
This is a nonuniform model of computation, C27 may have no relation whatsoever to C28.

Suppose NP is in P/poly and has a (non-uniform) circuit family that accepts it. Karp and Lipton show that NP in P/poly implies collapses in uniform models of computation as well.

Richard Karp and Richard Lipton, Some connections between nonuniform and uniform complexity classes, STOC 1980.

The main result shows that if NP is in P/poly then the polynomial hierarchy collapses to the second level, giving us evidence that NP is not in P/poly and hope that we can prove P≠NP by showing superpolynomial lower bounds on the circuit computing some NP problem.

The paper also gives a general (though controversial) definition of advice and a collapse of EXP to Σ2p∩Π2p if EXP is in P/poly (credited to Meyer), and similar results for PSPACE and the Permanent.

Kannan uses Karp-Lipton to show that some language in Σ2p∩Π2p does not have linear-size circuits, or more generally for every k, there is a language Lk in Σ2p∩Π2p that cannot be computed by nonuniform nk-size circuits.

Later extensions to Karp-Lipton:

  1. If NP in P/poly then the polynomial-time hierarchy collapses to S2P ⊆ ZPPNP ⊆ Σ2p∩Π2p. (see Cai and Köbler-Watanabe)
  2. If EXP, PSPACE or the Permanent is in P/poly then EXP, PSPACE or the Permanent is in MA ⊆ S2P respectively. (see Babai-Fortnow-Lund)
  3. If NP is in BPP (in P/poly) then the polynomial-time hierarchy is in BPP. (Zachos)
Using Kannan's proof, (1) implies that S2P does not have nk-size circuit for any fixed k. Can one improve (1) to show that if NP in P/poly then the polynomial-time hierarchy collapses to MA? This would imply MA does not have nk-size circuits for any fixed k.

No comments:

Post a Comment