Gibt es ein Orakel so dass ?

8

Hintergrund

Wir wissen, dass P#PPSPACE .

Außerdem wissen wir aus dem Satz von Toda, dass PHP#P .

Weitere Hintergrundinformationen zu #P finden Sie hier: https://en.wikipedia.org/wiki/Sharp-P

Frage

Gibt es ein Orakel A so dass (P#P)APSPACEA ?

Michael Wehar
quelle
3
Ich würde vermuten, dass für den ersten Teil das Setzen von A=PSPACE ausreichen sollte, oder? Stimmt es nicht, dass PSPACEPSPACE=PSPACE ?
Michael Lampis
@MichaelLampis Ja, wenn Sie den Platz auf dem Abfrageband zählen, dann klingt das für mich richtig! :)
Michael Wehar
Großartig, vielen Dank, dass Sie darauf hingewiesen haben! Ich habe die Frage geändert und den einfacheren Teil über das Finden eines Orakels entfernt, bei dem sie gleich sind. :)
Michael Wehar
5
Es gibt ein Orakel, das PP von PSPACE trennt: Jacobo Toran, Eine kombinatorische Technik zum Trennen von Zählkomplexitätsklassen, ICALP 1989. Das beste Ergebnis für P ^ PP, das ich kenne, ist ein bedingtes Ergebnis von Heribert Vollmer: Beziehung zwischen Polynomzeit und konstanter Tiefe. TCS, 207: 159-170, 1998.
Markus Bläser
1
@ MarkusBläser Ich denke du solltest dies als Antwort posten.
Emil Jeřábek

Antworten:

6

Auf vielfachen Wunsch hier mein Kommentar als Antwort:

Es gibt ein Orakel, das von trennt: Jacobo Toran, Eine kombinatorische Technik zum Trennen von Zählkomplexitätsklassen, ICALP 1989. Das beste Ergebnis für , das ich kenne ist ein bedingtes Ergebnis von Heribert Vollmer: Polynomzeit mit konstanter Tiefe in Beziehung setzen. TCS, 207: 159 & ndash; 170, 1998.P S P A C E P P P.PPPSPACEPPP

Markus Bläser
quelle
Ist bekannt, dass ist, um sicherzustellen, dass wir auf derselben Seite sind ? PPP=P#P
Michael Wehar
Es scheint einfach, dass , aber die andere Richtung scheint ein wenig schwierig. Sie führen eine binäre Suche durch, um die Anzahl der Lösungen für einen Verifizierer zu berechnen? PPPP#P
Michael Wehar
Ja, der Komplexitätszoo sagt, dass sie gleich sind. Ich denke auch, dass ich mich daran erinnere, dies vor einigen Jahren in einem Kurs zur Komplexitätstheorie als Übung bewiesen zu haben. :)
Michael Wehar
2
Der Komplexitätszoo sagt auch, dass meine Hauptfrage ein offenes Problem ist. Entschuldigung, das habe ich nicht bemerkt. Ich dachte, vielleicht hätte es jemand da draußen gelöst.
Michael Wehar