# Proof of Karp-Lipton theorem

I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009).

In particular, this book states the following:

Karp-Lipton theorem

If NP $\subseteq$ $P_{\backslash poly}$, then PH $= \Sigma^p_2$.

Proof: By Theorem 5.4, to show PH $= \Sigma^p_2$, it suffices to show that $\Pi^p_2\subseteq \Sigma^p_2$ and in particular it suffices to show that $\Sigma^p_2$ contains the $\Pi^p_2$-complete language $\Pi_2$SAT.

Theorem 5.4 states that

for every $i \geq 1$, if $\Sigma_i^p = \Pi_i^p$ then PH = $\Sigma_i^p$. That is, the hierarchy collapses to the ith level.

I am failing to understand how $\Pi^p_2\subseteq \Sigma^p_2$ implies $\Sigma_2^p = \Pi_2^p$.

As a more general question: does this hold for every $i$, i.e. does $\Pi^p_i\subseteq \Sigma^p_i$ imply $\Sigma_i^p = \Pi_i^p$ for all $i \geq 1$?

• After a while, if I remember correctly, we came to a vague explanation: "If $\Pi_2^p \subseteq \Sigma_2^p$, then we can transform a formula with quantifiers $\forall ... \exists$ to one with quantifiers $\exists ... \forall$, which we can use to transform a formula from $\Sigma_3^p$ of the form $\exists ... \forall ... \exists$ to one of the form $\exists... \exists... \forall$, which places it in $\Sigma_2^p$, which collapses the hierarchy. I am not sure that I understand this argument completely. – WardL Mar 30 '15 at 21:25
• another suggestion/ idea, the math statements switch between subset inclusion and equality (admit this is common in complexity theory). is there a way to stick to/ stdize on/ reformulate in one or the other? fyi Karp-Lipton thm / wikipedia – vzn Mar 31 '15 at 3:40

Recall that $L \in \Sigma_i^p$ iff $\bar{L} \in \Pi_i^p$. Suppose now that $\Sigma_i^p \subseteq \Pi_i^p$, and let $L \in \Pi_i^p$. Then $\bar{L} \in \Sigma_i^p$ and so $\bar{L} \in \Pi_i^p$ by assumption, implying that $L \in \Sigma_i^p$. In other words, $\Pi_i^p \subseteq \Sigma_i^p$, and so $\Sigma_i^p = \Pi_i^p$.
Here's why $L \in \Sigma_i^p$ iff $\bar{L} \in \Pi_i^p$. For concreteness, we take $i = 3$. By definition, $L \in \Sigma_3^p$ if for some P-time predicate $T$, $$x \in L \Leftrightarrow \exists |y| < |x|^{O(1)} \forall |z| < |x|^{O(1)} \exists |w| < |x|^{O(1)} T(x,y,z,w).$$ Similarly $\bar{L} \in \Pi_3^p$ if for some P-time predicate $S$, $$x \in \bar{L} \Leftrightarrow \forall |y| < |x|^{O(1)} \exists |z| < |x|^{O(1)} \forall |w| < |x|^{O(1)} S(x,y,z,w).$$ However, these two statements are equivalent, as a simple invocation of de Morgan's laws shows, together with the fact that P is closed under complementation (take $S = \lnot T$).