Beweis des Karp-Lipton-Theorems

14

Ich versuche, den Beweis des Karp-Lipton-Theorems zu verstehen, wie er im Buch "Computational Complexity: A modern approach" (2009) dargelegt ist.

In diesem Buch heißt es insbesondere:

Karp-Lipton-Theorem

Wenn NP , dann ist PH . Ppoly =Σ2p

Beweis: Nach Theorem 5.4 genügt es, um PH zu zeigen, dass und insbesondere zu zeigen, dass das -complete enthält Sprache SAT. Π=Σ2pΠ2pΣ2pΣ2pΠ2pΠ2

Satz 5.4 besagt das

für jedes , wenn dann PH = . Das heißt, die Hierarchie wird auf die i-te Ebene reduziert.Σ p i = Π p i Σ p ii1Σip=ΠipΣichp

Ich verstehe nicht, wie impliziert . Σ p 2 = Π p 2Π2pΣ2pΣ2p=Π2p

Als allgemeinere Frage gilt: Gilt dies für jedes , dh impliziert für alle ?Π p iΣ p i Σ p i = Π p i i 1ichΠipΣipΣip=Πipi1

WardL
quelle
Wenn ich mich richtig erinnere, kamen wir nach einer Weile zu einer vagen Erklärung: "Wenn , dann können wir eine Formel mit Quantifizierern in eine mit Quantifizierern umwandeln , mit dem wir eine Formel von des Formulars in eines der Formulare transformieren können , die Orte in , die die Hierarchie kollabiert ich bin nicht sicher , dass ich dieses Argument völlig verstehen... . . . . . Σ p 3. . . . . . . . . . . . Σ p 2Π2pΣ2p......Σ3p............Σ2p
WardL
Bei einem weiteren Vorschlag / einer Idee wechseln die mathematischen Aussagen zwischen Teilmengeneinschluss und Gleichheit (geben Sie zu, dass dies in der Komplexitätstheorie üblich ist). Gibt es eine Möglichkeit, sich an die eine oder andere zu halten / sie zu standardisieren / umzuformulieren? fyi Karp-Lipton thm / wikipedia
vzn

Antworten:

8

Denken Sie daran, dass iff . Nehmen wir nun an, dass , und lassen Sie . Dann und so durch Annahme, was impliziert, dass . Mit anderen Worten, und damit .LΣipL¯ΠipΣipΠipLΠipL¯ΣipL¯ΠipLΣipΠipΣipΣip=Πip

Hier ist, warum iff . Der Vollständigkeit halber nehmen wir . Per Definition , wenn für einige P-Zeit Prädikat , Ähnlich , wenn für ein p-time Prädikats , Diese beiden Aussagen sind jedoch äquivalent, wie ein einfacher Aufruf von de Morgans Gesetzen zeigt, zusammen mit der Tatsache, dass P unter Ergänzung (takeLΣ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).
S=¬T ).
Yuval Filmus
quelle