Beweis des Karp-Lipton-Theorems

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 . $\subseteq$ $P_{\backslash poly}$ $= \Sigma^p_2$

Beweis: Nach Theorem 5.4 genügt es, um PH zu zeigen, dass und insbesondere zu zeigen, dass das -complete enthält Sprache SAT. $= \Sigma^p_2$ $\Pi^p_2\subseteq \Sigma^p_2$ $\Sigma^p_2$ $\Pi^p_2$ $\Pi_2$

Satz 5.4 besagt das

für jedes , wenn dann PH = . Das heißt, die Hierarchie wird auf die i-te Ebene reduziert. $i \geq 1$ $\Sigma_i^p = \Pi_i^p$ $\Sigma_i^p$

Ich verstehe nicht, wie impliziert . $\Pi^p_2\subseteq \Sigma^p_2$ $\Sigma_2^p = \Pi_2^p$

Als allgemeinere Frage gilt: Gilt dies für jedes , dh impliziert für alle ? $i$ $\Pi^p_i\subseteq \Sigma^p_i$ $\Sigma_i^p = \Pi_i^p$ $i \geq 1$

complexity-theory complexity-classes 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..

Π_{2}^{p} \subseteq Σ_{2}^{p}

$\Pi_2^p \subseteq \Sigma_2^p$

\forall . . . \exists

$\forall ... \exists$

\exists . . . \forall

$\exists ... \forall$

Σ_{3}^{p}

$\Sigma_3^p$

\exists . . . \forall . . . \exists

$\exists ... \forall ... \exists$

\exists . . . \exists . . . \forall

$\exists... \exists... \forall$

Σ_{2}^{p}

$\Sigma_2^p$

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:

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

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 (take $L \in \Sigma_i^p$ $\bar{L} \in \Pi_i^p$ $i = 3$ $L \in \Sigma_3^p$ $T$

x \in L \Leftrightarrow \exists | y | < | x |^{O (1)} \forall | z | < | x |^{O (1)} \exists | w | < | x |^{O (1)} T (x, y, z, w) .

$x \in L \Leftrightarrow \exists |y| < |x|^{O(1)} \forall |z| < |x|^{O(1)} \exists |w| < |x|^{O(1)} T(x,y,z,w).$

\bar{L} \in Π_{3}^{p}

$\bar{L} \in \Pi_3^p$

S

$S$

x \in \bar{L} \Leftrightarrow \forall | y | < | x |^{O (1)} \exists | z | < | x |^{O (1)} \forall | w | < | x |^{O (1)} S (x, y, z, w) .

$x \in \bar{L} \Leftrightarrow \forall |y| < |x|^{O(1)} \exists |z| < |x|^{O(1)} \forall |w| < |x|^{O(1)} S(x,y,z,w).$

S = \neg T

$S = \lnot T$ ).

Yuval Filmus
quelle