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,
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.
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:
- If NP in P/poly then the polynomial-time hierarchy collapses to S2P ⊆ ZPPNP ⊆ Σ2p∩Π2p. (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 ⊆ S2P respectively. (see Babai-Fortnow-Lund)
- If NP is in BPP (in P/poly) then the polynomial-time hierarchy is in BPP. (Zachos)