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

54

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.

András Salamon
źródło
12
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
17
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 O stosunku do każdego oracle O tak, że P O = NP O . Zatem L jest w H, jeśli wyrażenie P = NPLOOOOL P relatywizuje. PH H Alternacje czasu ( O ( log log n ) , p O L Y ) . Z twierdzenia Tody i niektórych lematów w twierdzeniu Tody jest również prawdą, że H P m o d q P dla każdego q . (Zasadniczo każda wyrocznia spełniająca P O = NP O daje nową górną granicę H. Jest otwarte, czy H = PH.)L(O(loglogn),poly)modqPqOO
Russell Impagliazzo
4
@ Russell: dzięki! Ten komentarz brzmi jak odpowiedź.
András Salamon
5
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-8H
Joshua Grochow
3
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:

6

Z komentarza Russella Impagliazzo :

PP=NPHLHLPOOPO=NPOLHP=NPLPPHHAltTime(O(lglgn),poly)HPmodqPqPO=NPOHH=PH

I z komentarza Lance Fortnow :

f(n)HAltTime(f(n),poly)P=NPP=AltTime(f(n),poly)NPL

H

Kaveh
źródło
1
f(n)=lglgn
3
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
3
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
1
PO=NPOLLOOPONPOLO2Σ
Joshua Grochow
5

ΣkPk

MxyNP

Cook(M,n,t)Ms(n,t)polyMnt

P=NPAppoly

siisi+1=sp(si)kq(n)=(sp)k(n)n jest wielkością formuły TQBF podanej jako dane wejściowe.

kq(n)polyP

kω(1)q(n)n2O(k)k=lglgnk=lgn


C

TP=NPP=C
TZFCPNP

CHHPP=NP


BPP=PPIP=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