Dlaczego P = NP nie oznacza P = AP (tj. P = PSPACE)?

Powszechnie wiadomo, że jeśli wówczas hierarchia wielomianowa upadnie, a .$\mathbf{P}=\mathbf{NP}$$\mathbf{P}=\mathbf{PH}$

Można to łatwo zrozumieć indukcyjnie za pomocą maszyn Oracle. Pytanie brzmi - dlaczego nie możemy kontynuować procesu indukcyjnego poza stałym poziomem naprzemienności i udowodnić (aka )?$\mathbf{P}=\mathbf{AltTime}(n^{O(1)})$$\mathbf{AP}=\mathbf{PSPACE}$

Szukam intuicyjnej odpowiedzi.

Dowodem $\mathbf{P}=\mathbf{AltTime}(O(1))$ ( $=\mathbf{PH}$ ) jest indukcja stosując $\mathbf{P}=\mathbf{NP}$ . Indukcja pokazuje, że dla dowolnej liczby naturalnej $k$ , $\mathbf{P}=\mathbf{AltTime}(k)$ (i $\mathbf{AltTime}(O(1))$ to tylko ich związek).

Indukcja nie działa, gdy liczba naprzemienności może się zmieniać wraz z rozmiarem wejściowym (tj. Gdy liczba możliwych alternatyw maszyny nie jest liczbą, ale funkcją wielkości wejściowej, tzn. Nie pokazujemy, że wykonanie maszyny na jednym wejściu można zredukować do braku przemienności, pokazujemy, że wykonanie maszyny na wszystkich wejściach można „równomiernie” zredukować do braku przemienności).

Spójrzmy na podobne, ale prostsze stwierdzenie. Chcemy pokazać, że funkcja tożsamości ostatecznie dominuje nad wszystkimi stałymi funkcjami ( f ≪ g iff dla wszystkich, ale ostatecznie wiele n f ( n ) ≤ g ( n ) ). Można to udowodnić przez indukcję. Dla wszystkich k , k ≪ n (tj. F k ≪ i d gdzie f k ( n ) = $id(n)=n$$f \ll g$$n$ $f(n) \leq g(n)$$k$$k \ll n$$f_k \ll id$$f_k(n)=k$), ale nie mamy tego dla funkcji nie stałych, takich jak , n 2 ≪ ̸ n .$n^2$$n^2 \not \ll n$

Porównaj hierarchię wielomianową z hierarchią dla dowodów interaktywnych. Jeśli dla niektórych stałych k masz interaktywne k w dowodzie interaktywnym - IP ( k ) - wynikowa klasa złożoności ma nie więcej mocy niż to, co otrzymujesz z dwiema alternatywami - to znaczy, IP ( k ) = IP (2 ) = AM (przy założeniu k ≥2). Jeśli jednak dopuścisz wielomianową liczbę alternatyw, otrzymasz klasę złożoności IP = PSPACE, która, jak się uważa, jest znacznie większa niż AM, klasa jest zawarta w Π ₂ P, na drugim poziomie hierarchii wielomianowej. Zjawisko to faktycznie się dzieje (chociaż, o ile wiemy, z hierarchią wielomianową).

Dzieje się tak, ponieważ redukcja, która bierze problem rozmiaru nw IP ( k ) i zamienia go w problem w IP (2), wysadza rozmiar problemu, tak że podczas gdy dla konkretnego IP ( k ) problem pozostaje wielomianowy , jeśli pozwolisz k zmieniać, wynikowa redukcja nie daje problemów, które są wielomianowe w k .

Oto mała intuicja dotycząca przerwy między stałymi i nieograniczonymi naprzemiennościami: operacja wielomianowa powtarzana stałą liczbę razy jest wielomianowa, ale powtarzanie wielomianowej liczby razy może być wykładnicze. Na przykład weź mnożenie powtórzone na sobie:

v = 2
for(i=1 to n)
  v = v*v

Liczba iteracji jest liniowa, a dane wyjściowe są wykładnicze. Ale jeśli naprawisz n, jest to wielomian wielkości początkowej wartości.

Poniżej rozwijam nieco kwestię odpowiedzi Petera, próbując usunąć kwantyfikator przez więcej niż stałą liczbę kroków, aby zobaczyć, gdzie zawodzi i czy cokolwiek można uratować po takiej próbie.

Spróbujmy wzmocnić $\mathsf{P}=\mathsf{NP}$ więcej niż stałą liczbę razy.

Załóżmy, że $\mathsf{P}=\mathsf{NP}$ . Dlatego istnieje wielomianowa wehikuł czasu, który rozwiązuje Ext-Circuit-SAT (czy istnieje zadowalające rozszerzenie dla danego obwodu i częściowe przypisanie do jego wejść?).

Mówiąc bardziej formalnie, mamy algorytm wielogodzinny $A$ z wielomianowym czasem działania $p(n)\in\rm{poly}(n)$ st

Biorąc pod uwagę obwód boolowski $\varphi$ i częściowe przypisanie $\tau$ do wejść,
$A$ zwraca „tak”, jeśli istnieje rozszerzenie $\tau$ które spełnia $\varphi$ , a w przeciwnym razie zwraca „nie”.

Aby przejść przez stały czas, musimy skutecznie usunąć kwantyfikator. Możemy to zrobić, ponieważ Twierdzenie Cooka Twierdzenie to konstruktywne, w rzeczywistości daje czasie wielomianowym algorytm $Cook$ st

Biorąc DTM $M$ otrzymaniu dwóch wejść, oraz trzy jednoargumentowy liczby $n$ , $m$ i $t$ ,
$Cook(M, n, m, t)$ zwraca logiczny obwód rozmiaru $O(t^2)$ , która symuluje $M$ na wejściach długości $(n,m)$ dla $t$ kroków.

Spróbujmy wykorzystać do rozszerzenia argumentu dla $\mathsf{P}=\mathsf{PH}$ uzyskanie TQBF rozwiązywania algorytm (właściwie TQBCircuit, czyli Totally problemem Ilościowy Boolean obwodu).

Idea algorytmu jest następujący: to wielokrotne użycie $Cook$ na $A$ w celu usunięcia kwantyfikatorów z danego obwodu ilościowo. Istnieją numer liniowy kwantyfikatorów więc mamy nadzieję uzyskać algorytm czasu wielomianu (mamy algorytm z wielomianowo wielu kroków wykorzystujących czasie wielomianowym podprogramów $Cook$ ). Pod koniec tego procesu eliminacji kwantyfikatora będziemy mieli obwód bez kwantyfikatora, który można ocenić w czasie wielomianowym (problem z wartością obwodu jest w $\mathsf{P}$ , niech $CV$ będzie algorytmem wielomianowym do obliczania wartości obwodu w danym obwodzie) .

Zobaczymy jednak, że ten pomysł nie działa (z tego samego powodu, na który wskazał Piotr).

• Niech $\varphi$ będzie obwodem skwantyfikowanym (zainicjalizowanym do podanego wzoru skwantyfikowanego).
• Niech $k$ liczba kwantyfikatorów w $\varphi$ .

• Dla $i$ od $k$ do $1$ zrobić

  • Niech $\psi$ = $Qx_k \sigma(x_1,...,x_k)$ będzie ostatnim kwantyfikatora i kwantyfikator wolna część.

  • Jeśli $Q = "\exists"$ ,

    1. Oblicz $C = Cook(A, |\sigma|, |x_1|+...+|x_k-1|, p)$ ,
    2. Zastąp bity wejściowe $\sigma$ w obwodzie $C$ ,
    3. Wymienić $\psi$ z $C$ na $\varphi$ .

  • Jeśli $Q = "\forall"$ ,

    1. Rozważ $\psi$ jako $\lnot \exists x_k \lnot \sigma$ ,
    2. Oblicz $C = Cook(A, |\lnot \sigma|, |x_1|+...+|x_k-1|, p)$ ,
    3. Zamień bity wejściowe na $\lnot \sigma$ w obwodzie $C$ ,
    4. Zamień $\psi$ na $\lnot C$ w $\varphi$ .
• Oblicz i zwróć $CV(\varphi)$ .

Wynikowy algorytm wygląda na czas wielomianowy: mamy wielomian wiele kroków, każdy krok jest obliczalny w czasie wielomianowym. Jednak nie jest to poprawne, algorytm nie jest czasem wielomianowym.

Korzystanie z podprogramów czasu wielomianowego w algorytmie czasu wielomianowego jest czasem wielomianowym. Problem polega na tym, że generalnie nie musi to być prawdą, jeśli wartości zwracane przez podprogramy nie mają wielomianowego rozmiaru w oryginalnych danych wejściowych i zakładamy, że wykonujemy przypisania dotyczące wartości zwracanych z podprogramów. (W modelu TM musimy odczytywać dane wyjściowe dowolnego podprogramu wielomianowego bit po bicie). Tutaj wielkość zwracanej wartości z algorytmu $Cook$ rośnie (może być potęgą wielkości przekazanego jej wejścia , dokładna moc zależy od czasu przebiegu $A$ i wynosi około $p^2(|input|)$, skoro wiemy, że $A$ nie może być krótszy niż czas liniowy, $|output|$jest przynajmniej $|input|^2$ ).

Problem jest podobny do prostego kodu poniżej:

• Biorąc pod uwagę $x$ ,
• Niech $n = |x|$,
• Niech $y = x$ ,
• Dla $i$ od $1$ do $n$ zrobić
  • Niech $y = y^{|y|}$, (tj. konkatenacja $|y|$ kopii $y$ )
• Zwróć y

Za każdym razem, gdy wykonujemy $y = y^{|y|}$kwadratowy rozmiar $y$ . Po $n$ wykonaniach będziemy mieć $y$ które jest $x^{2^n}$ i ma rozmiar $n2^n$ , oczywiście nie jest wielomianem w wielkości wejściowej.

Załóżmy, że bierzemy pod uwagę tylko formuły kwantyfikowane z $k(n)$ przemianami kwantyfikatora (gdzie $n$ jest całkowitą wielkością formuły kwantyfikowanej).

Załóżmy, że $A$ jest uruchamiany w czasie $p$ (np liniowy czasu, który nie jest wykluczone, do tej pory), i być może bardziej skuteczne $Cook$ algorytm wyprowadzania mniejszy obwód wielkości $l(t)$ w miejsce $t^2$ , to uzyskać algorytm dla ExtCircuitSat działający w czasie $(l\circ p)^{O(k)}(n)=\underbrace{l(p(l(p(\dots(l(p(n)))))))}_{O(k)\mbox{ compositions}}$ . Nawet w przypadku, gdy zarówno$l$jaki$p$były liniowe (ale o współczynniku całkowitym$a\geq 2$) otrzymalibyśmy algorytm działający w czasie$\Omega(n2^{k(n)})$i gdyby$k(n) = \Theta(n)$to byłoby$\Omega(n2^n)$ podobny do algorytmu brutalnej siły (a nawet to było oparte na założeniu, że Cook-Levin można wykonać na algorytmach, uzyskując obwody o rozmiarach liniowych w czasie działania algorytmu).

Myślę, że dzieje się tak, ponieważ na każdym poziomie PH liczba zmian jest stała (tj. Niezależna od wielkości wejściowej), podczas gdy w AP liczba alternatyw może być nieograniczona (ale wielomianowa w wielkości wejściowej).