Ist

37

Wir wissen, dass die erste Ebene der Polynomhierarchie (dh NP und co-NP) in PP liegt und dass . Aus Todas Theorem wissen wir auch, dass . $PP \subseteq PSPACE$ $PH \subseteq P^{PP}$

Wissen wir, ob ? Wenn nicht, warum ist mit einem Orakel stärker als ? Ist es möglich, dass und ? $PH \subseteq PP$ $P$ $PP$ $PP$ $PH \nsubseteq PP$ $PP \nsubseteq PH$

Diese Frage ist sehr einfach, aber ich habe keine Ressourcen gefunden, die sich damit befassen.

Ich habe diese verwandte, aber viel weniger spezifische Frage zum mathematischen Überlauf gestellt, bevor ich mehr über das Thema erfahren habe.

Hier ist eine etwas verwandte (aber andere) Frage: Ist ? $coNP^{\#P}=NP^{\#P}=P^{\#P}$

Update: Schauen Sie sich hier Noam Nisans Frage an: Mehr zu PH in PP?

cc.complexity-theory counting-complexity polynomial-hierarchy Huck Bennett
quelle

37

Huck, wie Lance und Robin betonten, haben wir Orakel, bezüglich derer PH nicht in PP ist. Aber das beantwortet Ihre Frage nicht, wie die Situation in der "realen" (nicht relativen) Welt ist!

Die kurze Antwort ist, dass wir (wie bei so viel anderem in der Komplexitätstheorie) nicht wissen.

Die längere Antwort ist jedoch, dass es sehr gute Gründe gibt, anzunehmen, dass PH ⊆ PP tatsächlich ist.

Erstens impliziert Todas Theorem PH ⊆ BP.PP, wobei BP.PP die Komplexitätsklasse ist, die "zu PP wie BPP zu P ist" (mit anderen Worten, PP, wo Sie eine Randomisierung verwenden können, um zu entscheiden, welche MAJORITY-Berechnung Sie wollen) ausführen). Zweitens hätten wir unter plausiblen Derandomisierungshypothesen (ähnlich denen, von denen bekannt ist, dass sie P = BPP implizieren, von Nisan-Wigderson, Impagliazzo-Wigderson usw.) PP = BP.PP.

Nachtrag, um Ihre anderen Fragen zu beantworten:

(1) Ich würde sagen, dass wir in Bezug auf die Frage, ob PP = P ^{PP ist,} keine überzeugende Intuition haben . Aus den Ergebnissen von Beigel-Reingold-Spielman und Fortnow-Reingold wissen wir, dass PP unter nicht adaptiven (Wahrheitstabellen-) Reduktionen geschlossen wird. Mit anderen Worten, eine P-Maschine, die parallele Anfragen an ein PP-Orakel stellen kann, ist nicht leistungsfähiger als PP selbst. Die Tatsache, dass diese Ergebnisse für adaptive (nicht parallele) Abfragen an das PP-Orakel vollständig aufgeschlüsselt sind, legt jedoch nahe, dass letztere möglicherweise wirklich leistungsfähiger sind.

(2) NP ^PP und coNP ^{PP sind} möglicherweise noch leistungsfähiger als P ^PP . Und PP ^PP könnte noch mächtiger sein und so weiter. Die Sequenz P, PP, ^PP , PP ^PP , ^{PP ^ PP} usw. wird als Zählhierarchie bezeichnet , und so wie die Leute davon ausgehen, dass PH unendlich ist, kann man auch davon ausgehen (wenn auch mit weniger Vertrauen!), Dass CH ist unendlich. Dies hängt eng mit der Annahme zusammen, dass das Hinzufügen von mehr Schichten von Schwellenwertgattern in Schaltkreisen mit konstanter Tiefe (dh in neuronalen Netzen) zu mehr Rechenleistung führt.

Scott Aaronson
quelle

7

Scott, ich bin ein bisschen verwirrt von der Aussage, dass "plausibel" PP PH enthalten wird. Die erste Trennung von PH von PP über Orakel hat in ihrem kombinatorischen Kern die ursprüngliche Minski & Papert-Trennung, dass ein UND von ORs nicht durch ein Polylog-Grad-Schwellwertgatter simuliert werden kann. Ich denke, dass die uneinheitliche Version von Toda AC0 durch eine Wahrscheinlichkeitsverteilung über Polylog-Grad-Schwellgatter simuliert, die die richtige Antwort whp erhält. Auf der ungleichmäßigen Ebene fügt das "BP" -Tor im Gegensatz zu ungleichmäßigem P gegen BPP oder NP gegen AM eine signifikante Leistung hinzu. Also zum Beispiel ist PH in PP mit einem zufälligen Orakel?

Noam

Noam, enthält PP mit einem zufälligen Orakel nicht BP.PP? (Ich verstehe nicht, warum es nicht sollte.) Wenn ja, dann ist PH in PP mit zufälligem Orakel. Aber lassen Sie mich eine andere Frage stellen: Gibt es eine Komplexitätsklasse C, für die wir guten Grund zu der Annahme haben, dass C nicht gleich BP.C ist?

Scott Aaronson

Sie würden eine Verstärkung benötigen, um zu zeigen, dass PP = BP.PP mit einem zufälligen Orakel ist - ich verstehe nicht, wie das geht. Sogar ungleichmäßig kann ich nicht sehen, dass PH in PP / Poly ist. Würden die UND-Verknüpfungen, die sich nicht in der Polylog-Grad-Schwelle befinden, nicht darauf hindeuten, dass PH auch nicht einheitlich in PP enthalten ist?

Noam

Hier ist ein Artikel, der BP.PP = PP unter einer plausiblen Hypothese zeigt: www.cs.uwyo.edu/~jhitchco/papers/hhdcc.ps

Scott Aaronson

8

Was mir fehlte, war, dass Fortnow und Reingold zeigten, dass PP unter wahrheitsgetreuen Reduktionen geschlossen ist, ein Verschluss, der für die Derandomisierung mit einem PRG (oder ungleichmäßig oder mit einem zufälligen Orakel) benötigt wird. Allerdings bin ich hier immer noch verwirrt und habe eine Frage dazu formuliert: cstheory.stackexchange.com/questions/3331/more-on-ph-in-pp

Noam

23

Richard Beigel hat ein Orakel, zu dem nicht in PP enthalten ist. $P^{NP}$

Lance Fortnow
quelle

20

$P^{NP}$

[Ver] NK Vereshchagin. Über die Kraft von PP , Proceedings of IEEE Complexity'92, S. 138-143, 1992.

Robin Kothari
quelle

13

Was bisher noch nicht erwähnt wurde (soweit ich sehen kann) und was in der nicht relativen Welt gilt, ist Folgendes:

P H \subseteq P P if Q M A = P P .

$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$

Dies wurde von Vyalyi in diesem Artikel beobachtet und beruht auf der Stärkung zweier Theoreme:

$\sharp P$ $P$ $PH$
$QMA \subseteq PP$ $QMA$ $A_0PP$ $PP$

Alessandro Cosentino
quelle

Ist

Antworten: