Prueba del teorema de Karp-Lipton

Estoy tratando de entender la prueba del teorema de Karp-Lipton como se afirma en el libro "Complejidad computacional: un enfoque moderno" (2009).

En particular, este libro establece lo siguiente:

Teorema de Karp-Lipton

Si NP , entonces PH .P ∖ p o l y$\subseteq$ $P_{\backslash poly}$ $= \Sigma^p_2$

Prueba: según el teorema 5.4, para mostrar PH , es suficiente mostrar que y en particular es suficiente para mostrar que contiene el -completo idioma SAT. Π p 2 ⊆ Σ p 2 Σ p 2 Π p 2 Π $= \Sigma^p_2$$\Pi^p_2\subseteq \Sigma^p_2$$\Sigma^p_2$$\Pi^p_2$$\Pi_2$

El teorema 5.4 establece que

para cada , si entonces PH = . Es decir, la jerarquía colapsa al nivel i-ésimo.Σ p i = Π p $i \geq 1$$\Sigma_i^p = \Pi_i^p$$\Sigma_i^p$

No entiendo cómo implica . Σ p 2 = Π p $\Pi^p_2\subseteq \Sigma^p_2$$\Sigma_2^p = \Pi_2^p$

Como una pregunta más general: ¿esto vale para cada , es decir, implica para todo ?Π p i ⊆ Σ p i Σ p i = Π $i$$\Pi^p_i\subseteq \Sigma^p_i$ i≥$\Sigma_i^p = \Pi_i^p$$i \geq 1$

Recuerde que iff . Supongamos ahora que , y deje . Entonces y así por suposición, lo que implica que . En otras palabras, , y entonces .ˉ L ∈ Π p i Σ p i ⊆ Π p i L ∈ Π p i ˉ L ∈ Σ p i ˉ L ∈ Π p i L ∈ Σ p i Π p i ⊆ Σ p i Σ p i = Π p $L \in \Sigma_i^p$$\bar{L} \in \Pi_i^p$$\Sigma_i^p \subseteq \Pi_i^p$$L \in \Pi_i^p$$\bar{L} \in \Sigma_i^p$$\bar{L} \in \Pi_i^p$$L \in \Sigma_i^p$$\Pi_i^p \subseteq \Sigma_i^p$$\Sigma_i^p = \Pi_i^p$

He aquí por qué iff ˉ L ∈ Π p i . Para concreción, tomamos i = 3 . Por definición, L ∈ Σ T x ∈ L ⇔ ∃ | y | < | x | O ( 1 ) ∀ | z | < | x | O ( 1 ) ∃ | w | < | x | O ( 1 ) T ( x , y , z , w ) . ˉ L ∈ $L \in \Sigma_i^p$$\bar{L} \in \Pi_i^p$$i = 3$ si para algún predicado de tiempo P, De manera similar,if para algún predicado de tiempo P, $L \in \Sigma_3^p$$T$