[Solved]: Proof of Karp-Lipton theorem

Problem Detail: 

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$?

Asked By : WardL

Answered By : Yuval Filmus

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$).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40872

 Ask a Question

 Download Related Notes/Documents