Czy można wzmocnić P = NP poza P = PH?

W złożoności opisowej Immerman ma

Wniosek 7.23. Następujące warunki są równoważne:
1. P = NP.
2. Przekroczone, uporządkowane struktury, FO (LFP) = SO.

Można to uznać za „wzmocnienie” P = NP do równoważnego wyrażenia w (przypuszczalnie) większych klasach złożoności. Zauważ, że SO przechwytuje wielomianową hierarchię czasu PH, a FO (LFP) przechwytuje P, więc można to uznać za P = NP iff P = PH.

(Interesującą częścią tego jest stwierdzenie, że P = NP implikuje P = PH; trywialne jest, że P = CC implikuje P = NP dla dowolnej klasy CC zawierającej NP. Immerman po prostu zauważa „jeśli P = NP, to PH = NP” , przypuszczalnie dlatego, że P = NP może być użyte z definicją PH wyroczni, aby pokazać indukcyjnie, że cała hierarchia się zawali.)

Moje pytanie brzmi:

O ile jeszcze można w ten sposób wzmocnić P = NP?

W szczególności, jaka jest największa znana klasa CC 'taka, że ​​P = NP implikuje P = CC', a najmniejsza klasa CC taka, że ​​P = NP implikuje CC = NP? Umożliwiłoby to zastąpienie P = NP równoważnym pytaniem CC = CC '. P wydaje się być dość potężną klasą, która wydaje się zapewniać niewielką „przestrzeń wahadłową” dla argumentów próbujących oddzielić ją od NP: jak daleko można wzmocnić pomieszczenie wahadłowe?

Byłbym oczywiście również zainteresowany argumentem, który pokazuje, że P = PH jest granicą tego podejścia.

Edycja: zwróć uwagę na ściśle powiązane pytanie Dlaczego P = NP nie implikuje P = AP (tj. P = PSPACE)? który koncentruje się na drugim kierunku, dlaczego nie mamy dowodów, że P = PSPACE. Odpowiedzi tam napisane przez Kaveha i Petera Shora dowodzą, że liczba ustalonych alternatyw jest kluczowa. Kolejnym powiązanym pytaniem jest problem decyzyjny, o którym nie wiadomo, że jest w PH, ale będzie w P, jeśli P = NP, który pyta o problem kandydacki; tam również odpowiedzi można wykorzystać do skonstruowania odpowiedzi na to pytanie, chociaż klasy te są nieco sztuczne (dzięki Tsuyoshi Ito za zwrócenie na to uwagi). W bardziej ogólnym ustawieniu : Zwijanie maszyny Turinga związanej z czasem wolnym i przemiennym pyta, czy lokalne zwinięcie na dowolnym poziomie w hierarchii przemiennej powoduje zwinięcie w górę, jak to ma miejsce w przypadku hierarchii czasu wielomianowego.

Z komentarza Russella Impagliazzo :

$\mathsf{P}$$\mathsf{P}=\mathsf{NP}$$\mathsf{H}$$L$$\mathsf{H}$$L$$\mathsf{P}^O$$O$$\mathsf{P}^O=\mathsf{NP}^O$$L$$\mathsf{H}$$\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$$\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{poly})$$\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$$q$$\mathsf{P}^O=\mathsf{NP}^O$$\mathsf{H}$$\mathsf{H}=\mathsf{PH}$

I z komentarza Lance Fortnow :

$f(n)$$\mathsf{H}$$\mathsf{AltTime}(f(n),\mathsf{poly})$$\mathsf{P}=\mathsf{NP}$$\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$$\mathsf{NP}$$\mathsf{L}$

$\mathsf{H}$

• Kenneth W. Regan, „ Zbiory indeksów i prezentacje klas złożoności ”, 1999

$\Sigma^P_k$$k$

$M$$x$$y$$\mathsf{NP}$

$Cook(M, \vec{n}, t)$$M$$s(\vec{n},t) \in \mathsf{poly}$$M$$\vec{n}$$t$

$\mathsf{P}=\mathsf{NP}$$A$$p\in\mathsf{poly}$

$s_i$$i$$s_{i+1} = s\circ p(s_i)$$k$$q(n) = (s \circ p)^k(n)$$n$ jest wielkością formuły TQBF podanej jako dane wejściowe.

$k$$q(n) \in \mathsf{poly}$$\mathsf{P}$

$k \in \omega(1)$$q(n)$$n^{2^{O(k)}}$$k = \lg \lg n$$k = \lg n$

$C$

$C$$\mathsf{H}$$\mathsf{H}$$\mathsf{P}$$\mathsf{P}=\mathsf{NP}$

$\mathsf{BPP} = \mathsf{PP}$$\mathsf{IP} = \mathsf{PSpace}$

Uważam też, że istnieje tylko jeden prawidłowy sposób relatywizacji klasy złożoności, który powoduje wiele nieporozumień (jak myślenie o relatywizacji jako funkcjonalnej operacji na klasach złożoności w ich rozległym znaczeniu, relatywizacja jest modyfikacją modelu obliczeniowego , a nie klasa funkcji lub języków). Myślę, że oglądanie relatywizacji jako zmodyfikowanych (interaktywnych) ram obliczeniowych jest bardziej przydatne. W ten sposób istnieje wiele użytecznych sposobów relatywizacji klas złożoności (w sensie celowym). Aby uzyskać wszelkie informacje na temat nierelatywizowanego ustawienia z relatywizowanych ram, potrzebujemy pewnego rodzaju zasady przeniesienia podobnej do zasady przeniesienia w analizie niestandardowej. Zauważ, że wybranie określonej metody relatywizacji dla klas, która zachowuje znane relacje między klasami, nie daje nam zasady przenoszenia (jest to główne kryterium zwykle stosowane w literaturze do decydowania, co jest „właściwą” relatywizacją klasy).