Kann man P = NP über P = PH hinaus verstärken?

54

In der beschreibenden Komplexität hat Immerman

Folgerung 7.23. Die folgenden Bedingungen sind äquivalent:
1. P = NP.
2. Über endlichen, geordneten Strukturen ist FO (LFP) = SO.

Dies kann als "Verstärken" von P = NP auf eine äquivalente Aussage über (vermutlich) größere Komplexitätsklassen angesehen werden. Beachten Sie, dass SO die Polynom-Zeit-Hierarchie PH erfasst und dass FO (LFP) P erfasst, so dass dies als P = NP betrachtet werden kann, wenn P = PH.

(Der interessante Teil davon ist die Aussage, dass P = NP P = PH impliziert; es ist trivial, dass P = CC für jede Klasse CC, die NP enthält, P = NP impliziert. Immerman bemerkt einfach "wenn P = NP, dann PH = NP" vermutlich, weil P = NP mit der Oracle-Definition von PH verwendet werden kann, um induktiv zu zeigen, dass die gesamte Hierarchie zusammenbricht.)

Meine Frage ist:

Wie viel weiter kann P = NP auf diese Weise verstärkt werden?

Was ist insbesondere die größte bekannte Klasse CC ', so dass P = NP P = CC' impliziert, und die kleinste Klasse CC, so dass P = NP CC = NP impliziert? Dies würde es ermöglichen, P = NP durch die äquivalente Frage CC = CC 'zu ersetzen. P scheint eine ziemlich mächtige Klasse zu sein, die wenig "Wackelspielraum" für Argumente zu bieten scheint, die versuchen, sie von NP zu trennen: Wie weit kann der Wackelspielraum verstärkt werden?

Mich würde natürlich auch ein Argument interessieren, das zeigt, dass P = PH die Grenze dieses Ansatzes ist.


Bearbeiten: Beachten Sie die eng verwandte Frage Warum impliziert P = NP nicht P = AP (dh P = PSPACE)? was sich auf die andere Richtung konzentriert, warum wir keine Beweise dafür haben, dass P = PSPACE. In den Antworten von Kaveh und Peter Shor wird argumentiert, dass die Anzahl der festzulegenden Wechsel entscheidend ist. Eine andere verwandte Frage ist Ein Entscheidungsproblem, von dem nicht bekannt ist, dass es sich um ein PH-Problem handelt, das jedoch in P steht, wenn P = NP ist und nach einem Kandidatenproblem fragt. Die Antworten können auch verwendet werden, um Antworten auf diese Frage zu konstruieren, obwohl diese Klassen etwas künstlich sind (danke an Tsuyoshi Ito, der darauf hingewiesen hat). In einer allgemeineren Einstellung ist das Einklappen von Zeit und Wechsel begrenzt fragt, ob ein lokaler Kollaps auf einer beliebigen Ebene in einer Alternativhierarchie einen Aufwärtskollaps hervorruft, wie dies bei der Hierarchie der Polynomzeit der Fall ist.

András Salamon
quelle
17
Als eine Möglichkeit , zu formalisieren , welche Sprachen in P , wenn P = NP, Regan die Komplexitätsklasse H. Eine Sprache eingeführt in H ist , wenn und nur wenn L in P O im Verhältnis zu jedem Orakel O , so dass P O = NP O . Somit ist L in H, wenn die Aussage P = NP istLOOOOL P relativiert. PH H Wechselzeit ( O ( log log n ) , p o l y ) . Von Toda-Theorem, und einige der Lemmata in Toda-Theorem, ist es auch wahrdass H P m o d q P für jeden q . (Grundsätzlich gibt jedes Orakel, das P O = NP O erfüllt,eine neue Obergrenze für H. Es ist offen, ob H = PH.)L(O(LogLogn),pOly)mOdqPqOO
Russell Impagliazzo
4
@ Russell: danke! Dieser Kommentar klingt wie eine Antwort.
András Salamon
5
Schließlich wurde ein Verweis auf Ken Regans Klasse : siehe Definition 6.3 von "Indexmengen und Darstellungen von Komplexitätsklassen", verfügbar unter: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8927 . Offizielle Version unter: dx.doi.org/10.1016/0304-3975(95)00146-8H
Joshua Grochow
3
Sei f (n) eine beliebige unbegrenzte Funktion. H ist nicht in Alternations-Time (f (n), poly) enthalten und wenn Sie beweisen könnten, dass P = NP P = Alternations-Time (f (n), poly) impliziert, dann ist NP anders als L.
Lance Fortnow

Antworten:

6

Aus Russell Impagliazzos Kommentar :

Um zu formalisieren, welche Sprachen in wenn P = N P , führte Regan die Komplexitätsklasse H ein . Eine Sprache L ist genau dann in H, wenn L in Bezug auf jedes Orakel O in P O ist , so dass P O = N P O ist . Somit ist L in H, wenn die Aussage P = N P istPP=NPHLHLPOOPO=NPOLH relativiert. P HHA l t T i m e ( O ( lg lg n ) , p o l y ) . Von Toda-Theorem, und einige der Lemmata in Toda-Theorem, ist es auch wahrdass HP m o d q P für jeden q . Grundsätzlich gibt jedes Orakel, das P 0 = N P 0 erfüllt, eine neue Obergrenze anP=NPLPPHHEINltTichme(O(lglgn),pOly)HPmOdqPqPO=NPO . Es ist offenob H = P H .HH=PH

Und aus Lance Fortnows Kommentar :

Sei eine beliebige unbegrenzte Funktion. H ist nicht in enthaltenen A l t T i m e ( f ( n ) , p o l y ) und wenn man nachweisen kann P = N P bedeutet P = A l t T i m e ( f ( n ) , P o l y ) dann Nf(n)HEINltTichme(f(n),pOly)P=NPP=EINltTichme(f(n),pOly) ist anders als L .NPL

Zur Definition von siehe Definition 6.3 inH

Kaveh
quelle
1
@Josh, in Bezug auf Lances Kommentar habe ich das Gefühl, dass mir etwas fehlt, da unbegrenzt ist und AltTime (f, poly) laut Russels Kommentar H enthält. f(n)=lglgn
Kaveh
3
Ich bin über etwas verwirrt. Warum beantwortet Josh Grochows Antwort auf die frühere Frage zu diesem Thema ( cstheory.stackexchange.com/a/2039/1575 ) im Wesentlichen auch Regans Frage? Dh, warum gibt es nicht ein Beispiel für eine Sprache L, die in P ist, wenn P = NP, durch ein relativierendes Argument, aber das ist nicht in PH, wenn P! = NP? Und warum zeigt es deshalb nicht, dass wenn P! = NP, dann H streng größer als PH ist?
Scott Aaronson
3
Eigentlich fällt mir eine mögliche Antwort ein. Kommt es darauf an, dass bei Grochows Konstruktion die genaue Definition der Sprache L vom Orakel O abhängt?
Scott Aaronson
1
@Scott: In der Tat ist Ihre mögliche Antwort richtig, da es vom Orakel abhängt, welche Zeichenfolgen für die Diagonalisierung verwendet werden (und ob die in oder aus L gesetzt werden). Genauer gesagt ist die Sprache L endlich , wenn ist, so dass die verschiedenen L für verschiedene O nur endlich verschieden sind. Aber wenn man bedenkt , alle OS , so dass P ON P O , dann ist die L für diese unterschiedlichen O kann nicht einmal p-äquivalent, da dieser Satz von Orakeln eine dichte Teilmenge von ist 2 Σ * .PO=NPOLLOOPONPOLO2Σ
Joshua Grochow
5

Wie ich in schrieb meine Antwort auf die andere Frage wollen wir das Argument , konstruktive und einheitlich in der Anzahl der Wechsel machen durch einen Algorithmus zu geben , die löst unter der Annahme , dass wir ein Polynom-Algorithmus für SAT und sehen , was wir , wenn bekommen würde k ist nicht konstant.ΣkPk

Sei ein DTM mit zwei Eingängen x und y . Betrachten Sie es als Prüfer für ein N P Problem.MXyNP

Sei ein Algorithmus, der ein TM M in eine Schaltung der Größe s ( n , t ) p o l y umwandelt , die M an Eingängen der Größe n für t Schritte berechnet .COOk(M,n,t)Ms(n,t)pOlyMnt

Angenommen, und es gibt einen deterministischen Algorithmus A , der das Circuit-SAT-Zertifikaterweiterungsproblem in der Zeit p p o l y löst .P=NPEINppOly

Mit diesen Bestandteilen definieren wir einen Algorithmus für TQBF, der unter Angabe einer quantifizierten Booleschen Formel den innersten Quantifizierer rekursiv entfernt und durch einen quantifiziererfreien ersetzt. Let die Größe der Formel in der i - ten Schritt, dann haben wir s i + 1 = s p ( s i ) . Wenn die Formel k Quantifizierer hat, erhalten wir q ( n ) = ( s p ) k ( n ) mit nsichichsich+1=sp(sich)kq(n)=(sp)k(n)n ist die Größe der als Eingabe angegebenen TQBF-Formel.

Wenn konstant ist, dann q ( n ) p o l y . Da der Schaltungswert in P ist , haben wir einen Polynom-Zeit-Algorithmus.kq(n)pOlyP

Wenn dann ist q ( n ) keine Polynomzeit mehr, wir erhalten einen Algorithmus, der in n 2 O ( k ) ist . Wenn z. B. k = lg lg n ist, erhalten wir einen Algorithmus für die Quasipolynomialzeit. Für k = lg n erhalten wir nichts Nichttriviales.kω(1)q(n)n2O(k)k=lglgnk=lgn


Ich denke, was uns wirklich interessiert, ist die größte Klasse so dass T P = N PP = C ist, wobei T eine hinreichend starke Theorie ist, um alle unsere aktuellen Ergebnisse zu formalisieren (z. B. kann man annehmen, dass es Z F C ist ), weil Der Hauptpunkt dieser Ergebnisse ist es, den Nachweis von PN P zu erleichtern .C

TP=NPP=C
TZFCPNP

Wenn wir schwächere Theorien nehmen könnte das Ergebnis immer noch interessant sein, aber es ist auf dem größten Wert nicht wirklich eine obere Schranke ist . Wenn Regan H durch Relativierung definiert, beschränkt er die Argumente im Wesentlichen auf diejenigen, die relativieren. Wenn wir ein Ergebnis zu benutzen , die nicht relativieren nicht könnten wir eine größere Klasse als bekommen H , die gleich wäre , P , wenn P = N P .CHHPP=NP


Aus philosophischen Gründen lehne ich persönlich die Vorstellung ab, Relativierung als alternative Realitäten oder Welten zu betrachten. Aussagen in "relativierten Welten" allein geben uns keine Auskunft über die Aussage in nicht relativiertem Rahmen. Als ein Beispiel nehmen wir was die meisten von uns nicht für wahr halten, aber die relativierte Version ist wahr für ein zufälliges Orakel mit Wahrscheinlichkeit 1. Als ein anderes Beispiel nehmen wir I P = P S p a c e welches ist wahr, wird aber falsch für ein zufälliges Orakel mit der Wahrscheinlichkeit 1.BPP=PPichP=PSpeince

Ich finde auch die Idee, dass es nur einen einzigen korrekten Weg gibt, eine Komplexitätsklasse zu relativieren, der eine Menge Missverständnisse hervorruft (wie Relativierung als funktionale Operation auf Komplexitätsklassen in ihrem erweiterten Sinne zu denken, ist eine Relativierung eine Modifikation eines Rechenmodells , keine Klasse von Funktionen oder Sprachen). Ich halte es für nützlicher, Relativierungen als modifizierte (interaktive) Berechnungs-Frameworks anzusehen. Auf diese Weise gibt es viele nützliche Möglichkeiten, Komplexitätsklassen (in ihrem beabsichtigten Sinne) zu relativieren. Um aus einem relativierten Framework Informationen über die nicht-relative Einstellung zu erhalten, benötigen wir eine Art Übertragungsprinzip , das dem Übertragungsprinzip in der Nicht-Standard-Analyse ähnelt. Beachten Sie, dass die Auswahl einer bestimmten Relativierungsmethode für Klassen, bei der die bekannten Beziehungen zwischen Klassen erhalten bleiben, kein Übertragungsprinzip darstellt (dies sind die Hauptkriterien, anhand derer in der Literatur in der Regel entschieden wird, was die "richtige" Relativierung einer Klasse ist).

Kaveh
quelle
Ich bin damit einverstanden, "Relativierungen in gewisser Weise als ein interaktives Rechensystem anzusehen, das meiner Meinung nach nützlicher ist". Die Darstellung von Relativierungen könnte nämlich intuitiver verständlich gemacht werden, indem mit der Situation begonnen wird, in der die Maschine (n) (mit interaktivem Orakelzugriff) zuerst gegeben wird und ein Gegner eine Sprache für das Orakel auswählen darf. Dann wechselt man zu der Situation, in der zuerst eine (komplexe) Orakelsprache gegeben wird, und die Maschinen können nun an die Welt angepaßt werden, die durch das spezifische Orakel gegeben ist.
Thomas Klimpel