Ist Parity-P in PP enthalten?

Diese Frage stellte Jan Pax auf der Mailingliste Foundations of Mathematics . Sicherlich $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ aber ich vermute , aus den Antworten auf diese Frage , dass es nicht bekannt , ob $\oplus P \subseteq PP$ (sonst $PP$ wäre eine mögliche Antwort auf diese Frage). Wenn es nicht bekannt ist, gibt es eine Orakeltrennung?

cc.complexity-theory complexity-classes Timothy Chow
quelle

Wikipedia sagt, dass es ein Orakel gibt, für das

( R. Beigel, H. Buhrman und L. Fortnow. NP ist möglicherweise nicht so einfach als Erkennung einzigartiger Lösungen )

P^{A} = \oplus P^{A} \neq N P^{A} (= P P^{A}) = E X P^{A}

$P^A = \oplus P^A \neq NP^A ( = PP^A) = EXP^A$

Marzio De Biasi

Danke, Marzio. Ich denke, ich hätte genauer sein sollen: Gibt es ein Orakel

, das

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Timothy Chow

Was ich sagen werde, wird von den anderen Antworten zusammengefasst, kann aber nützlich sein, wenn Sie die Dinge einfach halten möchten. Das gesuchte Orakel ist nur eine Anwendung der altbekannten Tatsache, dass ein Perzeptron keine PARITÄT berechnen kann (Minsky & Papert).

Alessandro Cosentino

@AlessandroCosentino Ist

und

? Was wäre, wenn

wahr wäre?

P P^{\oplus P} = P P

$PP^{\oplus P}=PP$

{\oplus P}^{P P} = P P

${\oplus P}^{PP}=PP$

P P \subseteq \oplus P

$PP\subseteq\oplus P$

T ....

Antworten:

Ja, es gibt ein Orakel , so dass . In der Tat gibt es eine Oracle - , so daß . Das Ergebnis finden Sie im folgenden Artikel. $A$ $\oplus P^A \not\subseteq PP^A$ $A$ $\oplus P^A \not\subseteq PP^{PH^A}$

Frederic Grün, Ein Orakel Trennung von , Information Processing Letters, Band 37, Ausgabe 3, 18. Februar 1991, Seiten 149-153 $\oplus P$ $PP^{PH}$

Robin Kothari
quelle

Danke ... genau das habe ich gesucht! In den einleitenden Kommentaren zu seiner Arbeit schreibt Green Jacobo Toráns Ph.D. Diplomarbeit mit dem ersten Oracle -

, so daß

. Dieses Ergebnis wurde später als Theorem 5.13 in Toráns Arbeit "Complexity classes defined by counting quantifiers", JACM 38 (1991), 752–773, veröffentlicht.

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Timothy Chow

Scott Aaronson gibt ein Orakel , wo P = PEXP , die das Orakel impliziert Sie wollen. http://eccc.hpi-web.de/report/2005/040/download/ (Satz 12 im Anhang) $\oplus$

Lance Fortnow
quelle

Vielen Dank. Ich muss nur eine Antwort auswählen, um sie zu akzeptieren, also entscheide ich mich für Robin Kotharis Antwort, da es sich um eine frühere Referenz handelt.

Timothy Chow