Folgen von UP sind NP

19

BEARBEITEN am 08.02.2011: Nachdem ich einige Referenzen gefunden und gelesen hatte, entschloss ich mich, die ursprüngliche Frage in zwei separate zu unterteilen. Hier ist der Teil bezüglich UP vs NP, für den Teil syntaktische und semantische Klassen siehe Vorteile für syntaktische und semantische Klassen .


N PUP (die eindeutige Polynomzeit, siehe Wiki und den Zoo für Referenzen) ist definiert als Sprachen, die von -Maschinen mit einer zusätzlichen Einschränkung festgelegt werdenNP

  • Es gibt höchstens einen akzeptierenden Berechnungspfad für jede Eingabe.

Die genauen Beziehungen zwischen vs und vs sind noch offen. Wir wissen, dass Worst-Case-One-Way-Funktionen genau dann existieren, wenn , und es gibt Orakel in Bezug auf alle Möglichkeiten der Einschlüsse .U P U P N P PU P PU PN PPUPUPNPPUPPUPNP

Ich bin daran interessiert, warum vs eine wichtige Frage ist. Die Leute neigen dazu (zumindest in der Literatur ) zu glauben, dass diese beiden Klassen unterschiedlich sind, und mein Problem ist:N PUPNP

Wenn , sind "schlimme" Konsequenzen ?UP=NP

Es gibt einen verwandten Beitrag auf dem Komplexitätsblog im Jahr 2003. Und wenn ich das richtig verstehe, zeigt das Ergebnis von Hemaspaandra, Naik, Ogiwara und Selman, dass wenn

  • Es gibt eine -Sprache so dass es für jede erfüllbare Formel eine eindeutige erfüllbare Zuordnung mit in gibt. L x ( , x ) LNPLϕx(ϕ,x)L

dann kollabiert die Polynomhierarchie auf die zweite Ebene. Eine solche Implikation ist nicht bekannt, wenn gilt.UP=NP

Hsien-Chih Chang 張顯 張顯
quelle
(1) Es ist leicht zu erkennen (fast per Definition), dass UP und BPP vollständige Probleme haben, wenn sich „Probleme“ auf Versprechungsprobleme beziehen können. Es ist nicht bekannt, dass sie vollständige Sprachen haben . (2) Ich kenne die genaue Definition syntaktischer Klassen nicht. Ist PH syntaktisch? Es gibt kein vollständiges Problem (auch nicht mit Versprechen), wenn die Polynom-Hierarchie nicht zusammenbricht. (3) Ich kenne Ihre Verwendung der Notation "PromiseUP" nicht. Wenn NP die von einem NP-Rechner erkannte Klasse von Sprachen und PromiseUP die von einem UP-Rechner erkannte Klasse von Versprechungsproblemen bedeutet , können sie eindeutig nicht gleich sein.
Tsuyoshi Ito
@ Tsuyoshi: Danke für die Fragen. (1) Mit Problemen meine ich Sprachen , es ist meine Schuld, dass ich dies nicht klar schreibe. (2) Wir definieren syntaktische Klassen so, dass sie Blattsprachcharakterisierungen auf Mehrfachzeitmaschinen haben. PH ist etwas Besonderes, da keine Poly-Time-Leaf-Sprachcharakterisierung bekannt ist, bei der natürliche vollständige Sprachen garantiert sind. aber PH eine do haben logspace Blatt Sprache Charakterisierung. (mehr)
Hsien-Chih Chang 張顯 張顯
(Forts.) (3) Möglicherweise ist die Verwendung von PromiseUP nicht korrekt. Mit PromiseUP meine ich hier eine Klasse von Sprachen , so dass für yes-Instanzen der Computer einen eindeutigen Akzeptanzpfad hat und für no-Instanzen der Computer null oder mindestens zwei Akzeptanzpfade hat.
Hsien-Chih Chang 張顯 張顯
Danke für die Antwort. Was (3) betrifft, so kann ich aus einem flüchtigen Blick auf das Papier von Hemaspaandra, Naik, Ogihara und Selman keinen Weg finden, das Ergebnis in Bezug auf Entscheidungsprobleme zu formulieren. Übrigens ist die Verbindung zum Papier unterbrochen. Hier ist ein Link zur Journalversion .
Tsuyoshi Ito
2
Nur um sicherzugehen, dass PromiseUP völlig anders ist als das, was Sie beschrieben haben. Wie ich schrieb, ist PromiseUP die Promise-Problem-Version von UP; das heißt, es ist die Klasse von Versprechungsproblemen mit einer nicht-deterministischen Polynomzeit-Turing-Maschine M, so dass für Ja-Instanzen M genau ein Akzeptanzpfad und für Nein-Instanzen M keine Akzeptanzpfade vorliegen. Obwohl ich glaube, dass PromiseUP der traditionelle Name für diese Klasse ist, schreiben einige Leute (einschließlich ich) diese Klasse einfach als UP.
Tsuyoshi Ito

Antworten:

4

UP=NPSpanP=#PUP=NPSpanP=#P#PSpanP

Eine Funktion ist in wenn es eine Turingmaschine Wandler so dass für alle , ist die Anzahl der verschiedenen Ausgangssignale des auf Eingang .S P a n P N P M x f ( x ) M xf:ΣNSpanPNPMxf(x)Mx

J. Kobler, U. Schoning und J. Toran. Über Zählung und Annäherung , Acta Informatica, 26: 363-379, 1989.

Mohammad Al-Turkistany
quelle
2
Diese Antwort ( cstheory.stackexchange.com/a/20645/495 ) funktioniert auch hier, da bei die unzusammenhängende Paar-Vermutung falsch ist. N PUP=NPNP
Mohammad Al-Turkistany