# 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. Mar 30, 2015 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, 2015 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$).