Gibt es ein Orakel so dass ?

Hintergrund

Wir wissen, dass $P^{\#P} \subseteq PSPACE$ .

Außerdem wissen wir aus dem Satz von Toda, dass $PH \subseteq P^{\#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})^{A} \neq PSPACE^{A}$ ?

cc.complexity-theory complexity-classes oracles relativization pspace Michael Wehar
quelle

Ich würde vermuten, dass für den ersten Teil das Setzen von

A = PSPACE

$A=\textrm{PSPACE}$ ausreichen sollte, oder? Stimmt es nicht, dass

{PSPACE}^{PSPACE} = PSPACE

$\textrm{PSPACE}^{\textrm{PSPACE}} = \textrm{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

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

@ MarkusBläser Ich denke du solltest dies als Antwort posten.

Emil Jeřábek

Antworten:

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. $\mathrm{PP}$ $\mathrm{PSPACE}$ $\mathrm{P}^\mathrm{PP}$

Markus Bläser
quelle

Ist bekannt, dass ist, um sicherzustellen, dass wir auf derselben Seite sind ?

P^{P P} = P^{# P}

$P^{PP} = 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?

P^{P P} \subseteq P^{# P}

$P^{PP} \subseteq P^{\#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

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