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

_{0}, C_{1}, … where C_{n}has n inputs and at most n^k gates, such that and all x=x_{1}x_{2}…x_{n},x is in L iff C This is a nonuniform model of computation, C_{n}(x_{1},x_{2},…,x_{n})=1._{27}may have no relation whatsoever to C_{28}.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 Σ

_{2}^{p}∩Π_{2}^{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 Σ

_{2}^{p}∩Π_{2}^{p}does not have linear-size circuits, or more generally for every k, there is a language L_{k}in Σ_{2}^{p}∩Π_{2}^{p}that cannot be computed by nonuniform n^{k}-size circuits.Later extensions to Karp-Lipton:

- If NP in P/poly then the polynomial-time hierarchy collapses to S
_{2}^{P}⊆ ZPP^{NP}⊆ Σ_{2}^{p}∩Π_{2}^{p}. (see Cai and Köbler-Watanabe) - If EXP, PSPACE or
the Permanent is in P/poly then EXP, PSPACE or
the Permanent is in MA ⊆
S
_{2}^{P}respectively. (see Babai-Fortnow-Lund) - If NP is in BPP (in P/poly) then the polynomial-time hierarchy is in BPP. (Zachos)

_{2}^{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.

--

Posted by Lance to Computational Complexity at 11/19/2006 07:51:00 PM- If NP in P/poly then the polynomial-time hierarchy collapses to S