Bukti teorema Karp-Lipton

Saya mencoba memahami bukti teorema Karp-Lipton sebagaimana dinyatakan dalam buku "Kompleksitas Komputasi: Suatu pendekatan modern" (2009).

Secara khusus, buku ini menyatakan sebagai berikut:

Teorema Karp-Lipton

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

Bukti: Dengan Teorema 5.4, untuk menunjukkan PH , itu sudah cukup untuk menunjukkan bahwa dan khususnya itu sudah cukup untuk menunjukkan bahwa berisi -Lengkap bahasa 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$

Teorema 5.4 menyatakan itu

untuk setiap , jika maka PH = . Yaitu, hierarki runtuh ke tingkat engan.Σ p i = Π p $i \geq 1$$\Sigma_i^p = \Pi_i^p$$\Sigma_i^p$

Saya gagal memahami bagaimana menyiratkan . Σ p 2 = Π p $\Pi^p_2\subseteq \Sigma^p_2$$\Sigma_2^p = \Pi_2^p$

Sebagai pertanyaan yang lebih umum: apakah ini berlaku untuk setiap , yaitu apakah menyiratkan untuk semua ?$i$$\Pi^p_i\subseteq \Sigma^p_i$$\Sigma_i^p = \Pi_i^p$$i \geq 1$

Ingat bahwa iff . Misalkan sekarang , dan biarkan . Kemudian dan begitu dengan asumsi, menyiratkan bahwa . Dengan kata lain, , dan begitu .ˉ 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$

Inilah sebabnya iff . Untuk konkret, kita ambil i = 3 . Menurut definisi, L ∈ Σ p 3 jika karena P-waktu predikat T , Demikian pula jika untuk beberapa predikat -waktu , ˉ L ∈ Π p i x ∈ L ⇔ ∃ | y | < | x | O ( 1 ) ∀ | z | < | x | O ( 1 ) ∃ | w | < | x | O ( 1 ) T ( x , y , z , w $L \in \Sigma_i^p$$\bar{L} \in \Pi_i^p$$i = 3$$L \in \Sigma_3^p$$T$