Ist

Durch http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf

Wenn $A$ eine PSPACE-vollständige Sprache ist, $P^{A}=NP^{A}$ .

Wenn ein deterministisches Polynom-Zeit-Orakel ist, ist (unter der Annahme von ). $B$ $P^{B}\ne NP^{B}$ $P\ne NP$

ist die Klasse der Entscheidungsprobleme analog zu und , $PP$ $\#P$ $P\subseteq PP\subseteq PSPACE$

aber weder oder ist bekannt. Aber stimmt das? $P=PP$ $PP=PSAPCE$

? $coNP^{\#P}=NP^{\#P}=P^{\#P}$

cc.complexity-theory complexity-classes counting-complexity open-problem oracles Mike Chen
quelle

Wenn

ein deterministisches Polynomialzeit Orakel ist, ich denke , Sie meinen wir glauben

. (da

und

)

B

$B$

P^{B} \neq N P^{B}

$P^B \neq NP^B$

P^{B} = P

$P^B = P$

N P^{B} = N P

$NP^B = NP$

Ramprasad

Ich könnte mich irren, aber lassen Sie es mich versuchen: Ihre erste Frage geht davon aus, dass die zweite Einschränkung nicht streng ist. Mit anderen Worten, es wird angenommen, dass PP = PSPACE ist. In diesem Fall, denke ich, gilt die Gleichheit für das Ergebnis, das Sie zu Beginn erwähnt haben. Habe ich recht? (PS: Das Gegenteil gilt für die 2. Frage.)

MS Dousti

Todas Satz könnte hier relevant sein, da es eine gibt vielleicht in der Lage sein , den Unterschied zwischen falten

und

zum

Orakel. (Aber ich bin nicht 100% sicher.)

P

$P$

N P

$NP$

#P

$#P$

Boaz Barak

Die Antwort auf Ihre vierte Frage lautet ja. Sogar NP ^ PSPACE ist in PSPACE enthalten, also ist NP mit einem #P-Orakel mit Sicherheit in PSPACE enthalten.

Robin Kothari

Wie aus den Kommentaren hervorgeht, sind einige der in diesem Beitrag gestellten Fragen (und einige der Fragen, die Sie kürzlich hinzugefügt haben) grundlegend. Bitte zeigen Sie einige Beweise, dass Sie sich wirklich interessieren. Siehe auch meta.cstheory.stackexchange.com/questions/300/… , meta.cstheory.stackexchange.com/questions/300/… .

Tsuyoshi Ito

Antworten:

Es ist ein offenes Problem in der Komplexitätstheorie seit vielen Jahren , wenn Zusammenbruch, wobei die Polynomialzeit - Hierarchie ist. Es ist auch ein offenes Problem, ein Orakel zu konstruieren, um von zu trennen . $\mathsf{PH}^{\mathsf{\#P}}$ $\mathsf{PH}$ $\mathsf{P}^{\mathsf{\#P}}$ $\mathsf{PSPACE}$

Bin Fu
quelle

Willkommen bei CSTheory.SE, @Bin Fu! :)

Daniel Apon

Oder vielleicht waren Sie schon einmal hier, aber trotzdem willkommen! ;)

Daniel Apon

Danke, Daniel Apon. Es ist bekannt, dass PH ^ {Parity P} zusammenbricht. Es wird sehr interessant sein, wenn man nachweisen kann, dass PH ^ {# P} zusammenbricht.

Bin Fu

Interessant, könnten Sie eine Referenz für liefern

und das Problem ihres Zusammenbruchs, bitte?

P H^{# P}

$PH^{\#P}$

Neophyt

Von http://portal.acm.org/citation.cfm?id=116858

Wenn ich es nicht falsch interpretiere. Satz 4.1 (ii) sagt , " " und . $NP^{\mathbf{C}K}=\exists \mathbf{C}K$ $coNP^{\mathbf{C}K}=\forall\mathbf{C}K$

Lemma 3.4 (c) sagen : "Für jeden in Zählen Hierarchie, ". $K$ $\exists K\cup\forall K\subseteq\mathbf{C}K\subseteq\exists\mathbf{C}K\cap\forall\mathbf{C}K$

Ersetzen von , erhalten wir . $K$ $P$ $PP\subseteq\exists PP\cap\forall PP$

Was bedeutet , . $P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

Und gilt, wenn die Polynomhierarchie zusammenbricht und die Zählhierarchie zusammenbricht. $P^{\#P}=NP^{\#P}=coNP^{\#P}$

Mike Chen
quelle

Die Einbeziehung von P ^ X ⊆ NP ^ X ∩ coNP ^ X für jede Klasse X ergibt sich aus der Definition, und Sie benötigen hierfür keinen Satz 4.1 von Torán. Ich kann nicht verstehen, warum die Zusammenbrüche der Polynomhierarchie und der Zählhierarchie bedeuten, dass P ^ # P = NP ^ # P = coNP ^ # P. Können Sie näher darauf eingehen?

Tsuyoshi Ito

P = N P = c o N P

$P=NP=coNP$

P^{# P} = N P^{# P} = c o N P^{# P}

$P^{\#P}=NP^{\#P}=coNP^{\#P}$ . If the counting hierarchy collapses, then

C C P = C P

$\mathbf{C}\mathbf{C}P=\mathbf{C}P$ , i.e.

P P^{P P} = P P

$PP^{PP}=PP$ . By lemma 3.4(c),

\exists K \cup \forall K \subseteq C K

$\exists K\cup\forall K\subseteq\mathbf{C}K$ , so

P^{# P} \subseteq N P^{# P} \cap c o N P^{# P}

$P^{\#P}\subseteq NP^{\#P}\cap coNP^{\#P}$

\subseteq N P^{# P} \cup c o N P^{# P} \subseteq P P^{P P}

$\subseteq NP^{\#P}\cup coNP^{\#P}\subseteq PP^{PP}$

= P P = P^{# P}

$=PP=P^{\#P}$ , which means

\subseteq

$\subseteq$ in this formula should be

=

$=$ instead.

Mike Chen

“The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP.

Tsuyoshi Ito

In addition, P=NP does not imply P^#P=NP^#P as far as I know (but I may be missing something).

Tsuyoshi Ito

A common mistake in these type of arguments is to assume relativizing to an oracle is an operation on the collection of languages, but it is instead an operation ont the type of computation, which drastically affects what languages are in the class.

Derrick Stolee