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 C₀, C₁, … where C_n has n inputs and at most n^k gates, such that and all x=x₁x₂…x_n,

x is in L iff C_n(x₁,x₂,…,x_n)=1. This is a nonuniform model of computation, C₂₇ may have no relation whatsoever to C₂₈.

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 Σ₂^p∩Π₂^p 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 Σ₂^p∩Π₂^p does not have linear-size circuits, or more generally for every k, there is a language L_k in Σ₂^p∩Π₂^p that cannot be computed by nonuniform n^k-size circuits.

Later extensions to Karp-Lipton:

1. If NP in P/poly then the polynomial-time hierarchy collapses to S₂^P ⊆ ZPP^NP ⊆ Σ₂^p∩Π₂^p. (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 ⊆ S₂^P 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 S₂^P does not have n^k-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 n^k-size circuits for any fixed k.