Prova do teorema de Karp-Lipton

Estou tentando entender a prova do teorema de Karp-Lipton, conforme declarado no livro "Complexidade computacional: uma abordagem moderna" (2009).

Em particular, este livro declara o seguinte:

Teorema de Karp-Lipton

Se NP , PH .$\subseteq$ $P_{\backslash poly}$ = Σ p 2 $= \Sigma^p_2$

Prova: pelo Teorema 5.4, para mostrar PH , basta mostrar que e, em particular, basta mostrar que contém -complete idioma \ Pi_2 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$

O teorema 5.4 afirma que

para cada $i \geq 1$ , se $\Sigma_i^p = \Pi_i^p$ então PH = $\Sigma_i^p$ . Ou seja, a hierarquia cai para o i-ésimo nível.

Não estou conseguindo entender como implica . Σ p 2 = Π p $\Pi^p_2\subseteq \Sigma^p_2$$\Sigma_2^p = \Pi_2^p$

Como uma pergunta mais geral: isso vale para todo , isto é, implica para todos os ?$i$$\Pi^p_i\subseteq \Sigma^p_i$$\Sigma_i^p = \Pi_i^p$$i \geq 1$

Lembre-se de que iff ˉ L ∈ Π p i . Suponha agora que Σ p i ⊆ ¸ p i , e deixar L ∈ ¸ p i . Então ˉ L ∈ Σ p i e assim ˉ L ∈ ¸ p i por hipótese, o que implica que L ∈ Σ p i . Em outras palavras, Π p i ⊆ Σ p i , e assim$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$

Aqui está o porquê sse ˉ L ∈ ¸ p i . Para concretude, tomamos i = 3 . Por definição, L ∈ Σ p 3 , se por algum P-time predicado T , x ∈ L ⇔ ∃ | y | < | x | O ( 1 ) ∀ | z | < | x | O ( 1 )$L \in \Sigma_i^p$$\bar{L} \in \Pi_i^p$$i = 3$$L \in \Sigma_3^p$$T$ Da mesma forma ˉ L ∈ ¸ p 3 , se por algum tempo-P predicado S , x ∈ ˉ G ⇔ ∀ | y | < | x | O ( 1 ) ∃ | z | < | x |