Preuve du théorème de Karp-Lipton

14

J'essaie de comprendre la preuve du théorème de Karp-Lipton comme indiqué dans le livre "Computational Complexity: A modern approach" (2009).

En particulier, ce livre déclare ce qui suit:

Théorème de Karp-Lipton

Si NP Ppoly , alors PH =Σ2p .

Preuve: Par le théorème 5.4, pour montrer PH , il suffit de montrer que Π p 2Σ p 2 et en particulier il suffit de montrer que Σ p 2 contient le Π p 2 - langage complet Π 2 SAT.=Σ2pΠ2pΣ2pΣ2pΠ2pΠ2

Le théorème 5.4 déclare que

pour tout , si Σ p i = Π p i alors PH = Σ p i . Autrement dit, la hiérarchie s'effondre au ième niveau.i1Σip=ΠipΣip

Je n'arrive pas à comprendre comment implique Σ p 2 = Π p 2 .Π2pΣ2pΣ2p=Π2p

Comme question plus générale: cela vaut-il pour chaque , c'est-à-dire que Π p iΣ p i implique Σ p i = Π p i pour tout i 1 ?iΠipΣipΣip=Πipi1

WardL
la source
Après un certain temps, si je me souviens bien, nous sommes arrivés à une vague explication: « Si , alors on peut transformer une formule avec quantificateurs . . . une avec quantificateurs . . . , qui on peut utiliser pour transformer une formule de Σ p 3 de la forme . . . . . . l'une de la forme . . . . . . Π2pΣ2p......Σ3p............Σ2p
une autre suggestion / idée, les énoncés mathématiques basculent entre l'inclusion de sous-ensemble et l'égalité (admettez que c'est courant dans la théorie de la complexité). Existe-t-il un moyen de s'en tenir à / stdize sur / reformuler dans l'un ou l'autre? fyi Karp-Lipton thm / wikipedia
vzn

Réponses:

8

LΣipL¯ΠipΣipΠipLΠipL¯ΣipL¯ΠipLΣip. In other words, ΠipΣip, and so Σip=Πip.

Here's why LΣip iff L¯Πip. For concreteness, we take i=3. By definition, LΣ3p if for some P-time predicate T,

xL|y|<|x|O(1)|z|<|x|O(1)|w|<|x|O(1)T(x,y,z,w).
Similarly L¯Π3p if for some P-time predicate S,
xL¯|y|<|x|O(1)|z|<|x|O(1)|w|<|x|O(1)S(x,y,z,w).
However, these two statements are equivalent, as a simple invocation of de Morgan's laws shows, together with the fact that P is closed under complementation (take S=¬T).
Yuval Filmus
la source