14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – WardL Mar 30 '15 at 21:25
  • $\begingroup$ 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 $\endgroup$ – vzn Mar 31 '15 at 3:40
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.