Karp–Lipton theorem

Remarks

It suffices to show $\Pi_2^p \subseteq \Sigma_2^p$. Take a $\Pi_2^p$ language given by $x \in L \iff \forall y \, \exists z \, R(x, y, z)$ with $R$ in P and $y, z$ of polynomial length. The inner question "$\exists z \, R(x, y, z)$" is an NP question, so it reduces to the Boolean satisfiability problem, which by hypothesis has polynomial-size circuits. By self-reducibility one may take circuits that output a satisfying assignment whenever one exists. Then $x \in L$ if and only if there is such a circuit $C$ with the following property: for all $y$, the assignment that $C$ produces for the instance $(x, y)$ satisfies $R$. This is a $\Sigma_2^p$ condition, because a circuit that answers wrongly can only cause rejection.

Going deeper

For a student

Richard Karp and Richard Lipton published the result in 1980. The trick is that a guessed circuit can be checked: a wrong circuit for a self-reducible problem is caught, so guessing it costs only one existential quantifier. Later work improved the collapse, for example to $\mathrm{S}_2^p$ and to $\mathrm{ZPP}^{\mathrm{NP}}$. Since $\mathrm{BPP} \subseteq \mathrm{P/poly}$, the theorem also shows that if NP were contained in BPP, the hierarchy would collapse.