Folgen von UP sind NP

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 $\mathsf{UP}$ (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 werden$\mathsf{NP}$

• 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 P ≠ U P P ⊆ U P ⊆ N $\mathsf{P}$$\mathsf{UP}$$\mathsf{UP}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{UP}$$\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$

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 $\mathsf{UP}$$\mathsf{NP}$

Wenn , sind "schlimme" Konsequenzen ?$\mathsf{UP} = \mathsf{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 ) $\mathsf{NP}$$L$$\phi$$x$$(\phi,x)$$L$

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

$\mathsf{UP= NP}$$\mathsf{SpanP = \#P}$$\mathsf{UP= NP}$$\mathsf{SpanP = \#P}$$\mathsf {\#P}$$\mathsf {SpanP}$

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 $f : Σ^* →\mathbb N$$\mathsf{SpanP}$$\mathsf {NP}$$M$$x$$f(x)$$M$$x$

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