Ein Entscheidungsproblem, von dem nicht bekannt ist, dass es sich um PH handelt, das jedoch bei P = NP auftritt

28

Edit : Wie Ravi Boppana in seiner Antwort richtig hervorhob und Scott Aaronson in seiner Antwort ein weiteres Beispiel hinzufügte , stellte sich heraus, dass die Antwort auf diese Frage auf eine Weise "Ja" war, die ich überhaupt nicht erwartet hatte. Zuerst dachte ich, dass sie die Frage, die ich stellen wollte , nicht beantworteten , aber nach einiger Überlegung beantworten diese Konstruktionen mindestens eine der Fragen, die ich stellen wollte: „Gibt es eine Möglichkeit, ein bedingtes Ergebnis zu beweisen?“ P = NP ⇒ L ∈ P 'ohne das bedingungslose Ergebnis L ∈ PH zu beweisen ? ”Danke, Ravi und Scott!


Liegt ein Entscheidungsproblem L vor, so dass die folgenden Bedingungen beide erfüllt sind?

  • Es ist nicht bekannt, dass L in der Polynomhierarchie ist.
  • Es ist bekannt, dass P = NP L ∈ P impliziert .

Ein künstliches Beispiel ist so gut wie ein natürliches. Auch wenn ich den Buchstaben " L " verwende, kann es ein Versprechungsproblem anstelle einer Sprache sein, wenn es hilft.

Hintergrund . Wenn wir wissen, dass ein Entscheidungsproblem L in der Polynomhierarchie liegt , dann wissen wir, dass „P = NP ⇒ L ∈P“. Die Absicht der Frage ist, zu fragen, ob das Gegenteil zutrifft. Wenn eine Sprache L existiert, die die obigen beiden Bedingungen erfüllt, kann dies als Beweis dafür angesehen werden, dass die Umkehrung fehlschlägt.

Die Frage wurde von Joe Fitzsimons interessantem Kommentar zu meiner Antwort auf Walter Bishops Frage " Konsequenzen von #P = FP " motiviert .

Tsuyoshi Ito
quelle
Es ist immer schwierig, ein allgemeines Negativ zu beweisen, aber ich wäre überrascht, wenn es eine solche Sprache gäbe. Die verallgemeinerte Linial-Nisan-Vermutung (wenn sie wahr gewesen wäre) hätte nicht impliziert, was Sie verlangen, glaube ich nicht. Es hätte nur bedeutet, dass BQP nicht in PH enthalten war. Wenn PH zu P zusammengebrochen wäre, wäre BQP immer noch nicht in P (H) enthalten gewesen.
Daniel Apon
Fragen Sie sich, ob es eine Komplexitätsklasse X gibt. X ist keine Teilmenge von PH und P = NP -> X = P?
Philip White
@Philip: Ja, aber ich denke nicht, dass dies das Problem ändert, da wir normalerweise ein Entscheidungsproblem L in eine Klasse X von auf L reduzierbaren Entscheidungsproblemen umwandeln können. Zumindest war das meine Absicht, diese Frage im Hinblick auf Entscheidungsprobleme zu stellen .
Tsuyoshi Ito
Vielleicht möchten Sie zusätzlich zu Ihren aktuellen Anforderungen verlangen, dass die Sprache in irgendeiner Weise in der Nähe von PH liegt? Vielleicht sagen wir in PSPACE (obwohl es fraglich ist, wie nah PSPACE an PH ist; siehe S. Fenner, S. Homer, M. Schäfer, R. Pruim. Hyperpolynomhierarchien und der Polynomsprung. Theoretische Informatik. Band 262 ( 2001), S. 241-256 cse.sc.edu/~fenner/papers/hyp.pdf ). Oder vielleicht möchten Sie wirklich nach einer solchen natürlichen Sprache fragen . L
Joshua Grochow
@Joshua: Danke für den Kommentar und den Hinweis. Wie im Update (Revision 3) angegeben, habe ich jetzt die richtige Frage gestellt (im Gegensatz zu dem, was ich in Revision 2 hinzugefügt habe). Ich wollte wissen: "Gibt es eine Möglichkeit, ein bedingtes Ergebnis 'P = NP ⇒ L∈P' zu beweisen, ohne das unbedingte Ergebnis L∈PH zu beweisen?" ist eine Beweismethode, die sowohl für natürliche als auch für erfundene Beispiele gleichermaßen gelten sollte.
Tsuyoshi Ito

Antworten:

26

Da Ihnen eine künstliche Sprache nichts ausmacht, wie wäre es, wenn Sie definieren, dass leer ist, wenn P gleich NP ist, und das Halteproblem, wenn P nicht gleich NP ist. Okay, es ist ein kleiner Schummel, aber ich denke, Sie müssen das Problem umformulieren, um solche Schummel zu vermeiden. L

Ravi Boppana
quelle
5
Danke, ich verstehe den Punkt (definiere L = {M: Turingmaschine M hält an und P ≠ NP}). Natürlich beantwortet dies nicht das, was ich fragen wollte, aber ich denke, dass ich mehr nachdenken muss, um die Frage zu formulieren, die ich richtig stellen wollte.
Tsuyoshi Ito
30

Wenn ein künstliches Beispiel wirklich so gut ist wie ein natürliches, dann kann ich in der Tat ein solches Beispiel liefern!

Edit: Außerdem ist mein Beispiel "etwas" weniger betrügerisch als das von Ravi Boppana vorgeschlagene (wobei wir L als leere Sprache betrachten, wenn P = NP, und ansonsten das Halteproblem), indem ich die Sprache definiere L durch Angabe einer endlichen Prozedur, um zu entscheiden, ob L für eine Eingabe x ist. Zu keinem Zeitpunkt wird entschieden, ob x∈L die Lösung einer "unbegrenzten" mathematischen Frage wie P gegen NP erfordert.x


Ohne weiteres: Sei eine Aufzählung von polytime Turing-Maschinen. Für alle sei das lexikographisch erste , das 3SAT für alle Eingaben mit einer Länge von oder weniger korrekt entscheidet . Definieren Sie dann die Sprache L wie folgt: Für alle Eingaben der Größe , L, wenn und nur wenn die mit codierte Turing-Maschine höchstens Schritte dauert, wenn sie auf einem leeren Band ausgeführt wird.M1,M2,...nMt(n)Minxnxxnt(n)

Anspruch 1: Wenn P = NP, dann L P.

Beweis: Wenn P = NP, dann gibt es ein festes , das 3SAT für alle Eingaben löst; daher für alle . QEDMit(n)in

Anspruch 2: Wenn P NP, dann L P.

Beweis: Wenn ungebunden zunimmt, können wir einfach den Zeithierarchiesatz anwenden. QEDt(n)

Nun ist nicht nur L nicht in P, wenn man P NP annimmt : man nimmt an, dass es nicht in PH (oder sogar PSPACE) wäre!

Im Übrigen frage ich mich, ob jemand die obige Konstruktion verbessern kann, um eine Sprache L zu erhalten, die in P ist, wenn P = NP, aber nachweislich nicht in PH oder PSPACE, wenn P NP?

Scott Aaronson
quelle
1
Vielen Dank! Ich war nicht in der Lage, die Konstruktion so zu modifizieren, dass die Nichtmitgliedschaft bei PH nachweisbar ist, aber dies reicht aus, um mich davon zu überzeugen, dass das Hinzufügen der Bedingung, dass L entscheidbar ist, mit einem konstruktiven Nachweis der Entscheidbarkeit die Situation wahrscheinlich nicht wesentlich ändern wird. Hmm.
Tsuyoshi Ito
3
Ich werde Ravi Boppanas Antwort akzeptieren, weil er der erste war, der ankam, obwohl ich beides akzeptieren möchte, weil beide mir mehr Verständnis für das Problem verschafft haben. Ich hoffe, dass du verstehst….
Tsuyoshi Ito
4
Nett. Das ist eine großartige Antwort.
Daniel Apon
@Tyson Williams: Nur für den Fall, dass Sie es nicht bemerkt haben, seien Sie bitte sehr vorsichtig, um keinen Fehler einzuführen, wenn Sie einen Beitrag von anderen Benutzern bearbeiten. Es war ein Glück, dass Joe es bemerkte und korrigierte.
Tsuyoshi Ito
18

Beantworte Scott Aaronsons Frage, aber ein bisschen zu lang für einen Kommentar, hier ist eine Konstruktion einer Sprache so dass impliziert , aber impliziert .LP=NPLPPNPLPH

Sei und wie in Scotts Konstruktion. Wir machen es so, dass nicht für jedes auf reduziert , sondern nur dann, wenn (dh wenn ). Der Bau verläuft stufenweise. Im Stadium (unter Verwendung einer leicht berechenbaren und leicht umkehrbaren Bijektion ) stellen wir sicher, dass keine 1- Reduktion von nach ist . Sei die kleinste Ganzzahl, so dassM1,M2,M3,t(n)LΣkSATkt(n)PNPs=(i,j)ΣΣ×ΣMiLΣjSATnst(ns)>t(ns1)(Basisfall: ). Wenn es eine solche ganze Zahl , dann setze . Wenn es keine solche ganze Zahl , lassen wir für immer leer.n0=1nsL(1ns)=1ΣkSAT(Mi(1ns))nsL

Wenn , dann als , so gibt es immer ein solches , daher ist nicht in . Wenn , dann meine ist nur endlich unterscheidet sich von Scotts und ist daher in .PNPt(n)nnsLPHP=NPLLP

Joshua Grochow
quelle
Vielen Dank für Ihre Antwort, aber ich bin nicht sicher, ob ich den Aufbau verstehe. Es scheint mir, dass es für die Berechnung von notwendig sein könnte, auf unbestimmte Zeit zu suchen, und daher scheint es mir, dass wir keinen expliziten Algorithmus zur Entscheidung der Sprache L haben. Wenn wir keinen expliziten Algorithmus benötigen, zeigt die Antwort von Ravi Boppana dass es eine Sprache L gibt, so dass P = NP⇒L∈P und P ≠ NP⇒L∉R (dh L ist unentscheidbar). ns
Tsuyoshi Ito
1
@ Tsuyoshi Ito: Ich glaube nicht, dass Sie gegebene berechnen müssen, um L zu entscheiden; alles , was Sie tun müssen , ist, an Eingang , zu entscheiden , ob der Form ist für einige , und herauszufinden , welche es (falls vorhanden) ist. Gehen Sie wie folgt vor: Berechnen Sie bei Eingabe von und für alle . Wenn es ein so dass , dann ist nicht für irgendein , so dass . Ansonsten finde heraus, auf welcher Stufe s 1 n n n n n n 1 n t ( n ) t ( m ) , m < n m < n t ( n ) = t ( m ) n n s s L ( 1 n ) = 0 s n s t L ( 1 n )nss1nnnsss1nt(n)t(m)m<nm<nt(n)=t(m)nnssL(1n)=0s entspricht diesem (was getan werden kann, da Sie alle vorherigen Werte von berechnet haben) und berechnet dann wie in der Antwort beschrieben. nstL(1n)
Joshua Grochow