Karp-Lipton theorem

Statement

Statement in terms of complexity classes

The theorem has the following equivalent formulations. Pick any equivalent formulation of the conditional -- the theorem states that that implies any equivalent formulation of the conclusion.

Equivalent formulations of the conditional:

1. NP is contained in P/poly
2. The problem 3-SAT is contained in P/poly.
3. co-NP is contained in P/poly.

Equivalent formulations of the conclusion:

1. The class $\Sigma _{2}P$ (i.e., Sigma2P) is self-complementary, i.e., it equals its complementary class $\Pi _{2}P$ (i.e., Pi2P).
2. PH collapses to $\Sigma _{2}P$.
3. PH collapses to $\Pi _{2}P$.

Loose philosophical statement

Deterministic solution of a problem using length-specific advice $\to$ Nondeterministic solution by pushing the advice inside an additional existential quantifier

Related facts

• Adleman's theorem states that BPP is in P/poly.
• The Karp-Lipton theorem and Adleman's theorem together imply that BPP equals Sigma2P implies BPP equals PH