Bukti teorema Karp-Lipton

14

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 PhalHaily =Σ2hal

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 Π 2=Σ2pΠ2pΣ2pΣ2pΠ2pΠ2

Teorema 5.4 menyatakan itu

untuk setiap , jika maka PH = . Yaitu, hierarki runtuh ke tingkat engan.Σ p i = Π p ii1Σip=ΠipΣip

Saya gagal memahami bagaimana menyiratkan . Σ p 2 = Π p 2Π2pΣ2pΣ2p=Π2p

Sebagai pertanyaan yang lebih umum: apakah ini berlaku untuk setiap , yaitu apakah menyiratkan untuk semua ?iΠipΣipΣip=Πipi1

WardL
sumber
Setelah beberapa saat, jika saya ingat dengan benar, kami sampai pada penjelasan yang tidak jelas: "Jika , maka kita dapat mengubah rumus dengan penjumlah menjadi satu dengan penjumlahan , yang dapat kita gunakan untuk mengubah rumus dari dari formulir \ ada ... \ forall ... \ ada ke salah satu bentuk \ ada ... \ ada ... \ forall , yang menempatkannya di \ Sigma_2 ^ p , yang meruntuhkan hierarki. Saya tidak yakin bahwa saya memahami argumen ini sepenuhnya. . . . . . Σ p 3. . . . . . . . . . . . Σ p 2Π2pΣ2p......Σ3p............Σ2p
WardL
saran / ide lain, pernyataan matematika beralih antara subset inklusi dan kesetaraan (akui ini biasa dalam teori kompleksitas). apakah ada cara untuk tetap berpegang pada / merumuskan / merumuskan kembali dalam satu atau yang lain? fyi Karp-Lipton thm / wikipedia
vzn

Jawaban:

8

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 iLΣipL¯ΠipΣipΠipLΠipL¯ΣipL¯ΠipLΣipΠipΣipΣip=Πip

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ΣipL¯Πipi=3LΣ3pT

xL|y|<|x|O(1)|z|<|x|O(1)|w|<|x|O(1)T(x,y,z,w).
L¯Π3pS
xL¯|y|<|x|O(1)|z|<|x|O(1)|w|<|x|O(1)S(x,y,z,w).
Namun, kedua pernyataan ini setara, seperti yang ditunjukkan oleh doa de Morgan yang sederhana, bersama dengan fakta bahwa P ditutup dengan komplementasi (ambil ).S=¬T
Yuval Filmus
sumber