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_2subseteq 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_2subseteq 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_isubseteq Sigma^p_i$ imply $Sigma_i^p = Pi_i^p$ for all $i geq 1$?
Asked By : WardL
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
Related
