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.

cc.complexity-theory reference-request complexity-classes conditional-results polynomial-hierarchy András Salamon
źródło

Powiązane (bezwstydna autopromocja): Problem decyzyjny, o którym nie wiadomo, że jest w PH, ale będzie w P, jeśli P = NP .

Tsuyoshi Ito

Jako sposób formalizacji jakie języki są w P czy P = NP, Regan wprowadził klasa złożoności H. język

jest w H wtedy i tylko wtedy, gdy L jest w P

stosunku do każdego oracle

tak, że P

= NP

. Zatem

jest w H, jeśli wyrażenie P = NP

L

$L$

^{O}

$^O$

O

$O$

^{O}

$^O$

^{O}

$^O$

L

$L$

P relatywizuje. PH

Alternacje czasu

. Z twierdzenia Tody i niektórych lematów w twierdzeniu Tody jest również prawdą, że H

dla każdego

. (Zasadniczo każda wyrocznia spełniająca P

= NP

daje nową górną granicę H. Jest otwarte, czy H = PH.)

⟹ L \in

$\implies L \in$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

(O (\log \log n), p o l y)

$(O(\log \log n), \rm{poly})$

\subseteq

$\subseteq$

^{{m o d}_{q} P}

$^{\rm{mod}_q \rm{P}}$

q

$q$

^{O}

$^O$

^{O}

$^O$

Russell Impagliazzo

@ Russell: dzięki! Ten komentarz brzmi jak odpowiedź.

András Salamon

W końcu znalazłem odniesienie do klasy

Kena Regana : patrz definicja 6.3 „Zestawów indeksów i prezentacji klas złożoności”, dostępna na stronie: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Oficjalna wersja: dx.doi.org/10.1016/0304-3975(95)00146-8

H

$H$

Joshua Grochow

Niech f (n) będzie dowolną nieograniczoną funkcją. H nie jest zawarty w Alternations-Time (f (n), poly), a jeśli mógłbyś udowodnić, że P = NP oznacza P = Alternations-Time (f (n), poly), to NP różni się od L.

Lance Fortnow

Odpowiedzi:

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

Kaveh
źródło

f (n) = \lg \lg n

$f(n) = \lg \lg n$

Jestem z czegoś zmieszany. Dlaczego odpowiedź Josha Grochowa na wcześniejsze pytanie na ten temat ( cstheory.stackexchange.com/a/2039/1575 ) zasadniczo nie odpowiada również na pytanie Regana? To znaczy, dlaczego nie podaje przykładu języka L, który jest w P, jeśli P = NP za pomocą argumentu relatywizującego, ale nie ma go w PH, jeśli P! = NP? Dlaczego więc nie pokazuje, że jeśli P! = NP, to H jest ściśle większy niż PH?

Scott Aaronson

Właściwie przychodzi mi do głowy możliwa odpowiedź. Czy kwestia, że w konstrukcji Grochowa sama definicja języka L będzie zależała od wyroczni O?

Scott Aaronson

P^{O} = N P^{O}

$P^O = NP^O$

L

$L$

L

$L$

O

$O$

O

$O$

P^{O} \neq N P^{O}

$P^O \neq NP^O$

L

$L$

O

$O$

2^{Σ^{*}}

$2^{\Sigma^*}$

Joshua Grochow

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

T ⊢ P = N P \to P = C

$T \vdash \mathsf{P} = \mathsf{NP} \to \mathsf{P}=C$

T

$T$

Z F C

$\mathsf{ZFC}$

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$

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

Kaveh
źródło

Zgadzam się z tym, że „przeglądanie relatywizacji jako interaktywnych ram obliczeniowych jest moim zdaniem bardziej przydatne” w pewien sposób. Mianowicie prezentację relatywizacji można uczynić bardziej intuicyjną, zaczynając od sytuacji, w której maszyna (maszyny) z interaktywnym dostępem do wyroczni jest podana jako pierwsza, a przeciwnik może wybrać język wyroczni. Następnie przechodzimy do sytuacji, w której najpierw podaje się (złożony) język wyroczni, a maszyny można teraz dostosować do świata określonego przez wyrocznię.

Thomas Klimpel