Dowód twierdzenia Karpa-Liptona

Próbuję zrozumieć dowód twierdzenia Karp-Lipton, jak stwierdzono w książce „Złożoność obliczeniowa: nowoczesne podejście” (2009).

W szczególności ta książka stwierdza, co następuje:

Twierdzenie Karpa-Liptona

Jeśli NP , to PH .P ∖ p o l y$\subseteq$ $P_{\backslash poly}$ $= \Sigma^p_2$

Dowód: Zgodnie z twierdzeniem 5,4, w celu wykazania pH , to wystarczy, aby pokazać, że w szczególności wystarcza, aby pokazać, że zawiera -Complete język 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$

Twierdzenie 5.4 stwierdza, że

dla każdego , jeśli to PH = . Oznacza to, że hierarchia upada na i-ty poziom.Σ p i = Π p i Σ p $i \geq 1$$\Sigma_i^p = \Pi_i^p$$\Sigma_i^p$

Nie rozumiem, jak implikuje . Σ p 2 = Π p $\Pi^p_2\subseteq \Sigma^p_2$$\Sigma_2^p = \Pi_2^p$

Jako bardziej ogólne pytanie: czy dotyczy to każdego , tj. Czy oznacza dla wszystkich ?$i$$\Pi^p_i\subseteq \Sigma^p_i$$\Sigma_i^p = \Pi_i^p$$i \geq 1$

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

$L \in \Sigma_i^p$$\bar{L} \in \Pi_i^p$$i = 3$$L \in \Sigma_3^p$$T$