Dowód twierdzenia Karpa-Liptona

Próbuję zrozumieć dowód twierdzenia Karp-Lipton, jak stwierdzono w książce „Złożoność obliczeniowa: nowoczesne podejście” (2009).

W szczególności ta książka stwierdza, co następuje:

Twierdzenie Karpa-Liptona

Jeśli NP , to PH . $\subseteq$ $P_{\backslash poly}$ $= \Sigma^p_2$

Dowód: Zgodnie z twierdzeniem 5,4, w celu wykazania pH , to wystarczy, aby pokazać, że w szczególności wystarcza, aby pokazać, że zawiera -Complete język SAT. $= \Sigma^p_2$ $\Pi^p_2\subseteq \Sigma^p_2$ $\Sigma^p_2$ $\Pi^p_2$ $\Pi_2$

Twierdzenie 5.4 stwierdza, że

dla każdego , jeśli to PH = . Oznacza to, że hierarchia upada na i-ty poziom. $i \geq 1$ $\Sigma_i^p = \Pi_i^p$ $\Sigma_i^p$

Nie rozumiem, jak implikuje . $\Pi^p_2\subseteq \Sigma^p_2$ $\Sigma_2^p = \Pi_2^p$

Jako bardziej ogólne pytanie: czy dotyczy to każdego , tj. Czy oznacza dla wszystkich ? $i$ $\Pi^p_i\subseteq \Sigma^p_i$ $\Sigma_i^p = \Pi_i^p$ $i \geq 1$

complexity-theory complexity-classes

— WardL
źródło

Po pewnym czasie, jeśli dobrze pamiętam, doszliśmy do niejasnego wyjaśnienia: „Jeśli , możemy przekształcić formułę z kwantyfikatorami na formułę z kwantyfikatorami , którego możemy użyć do przekształcenia formuły z formularza do jednej z form , który umieszcza go w , co hierarchię. Nie jestem pewien, czy rozumiem ten argument całkowicie.

Π_{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

Inna sugestia / pomysł, stwierdzenia matematyczne przełączają między włączeniem podzbioru a równością (przyznaj, że jest to powszechne w teorii złożoności). czy istnieje sposób, aby trzymać się / przełożyć / przeformułować w jednym lub drugim? fyi Karp-Lipton thm / wikipedia

— od

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

$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
źródło