Ist

12

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

Wenn A eine PSPACE-vollständige Sprache ist, PA=NPA .

Wenn ein deterministisches Polynom-Zeit-Orakel ist, ist P BN P B (unter der Annahme von P N P ).BPBNPBPNP

ist die Klasse der Entscheidungsprobleme analog zu # P und P P P P S P A C E ,PP#PPPPPSPACE

aber weder oder P P = P S A P C E ist bekannt. Aber stimmt das?P=PPPP=PSAPCE

?coNP#P=NP#P=P#P

Mike Chen
quelle
1
Wenn ein deterministisches Polynomialzeit Orakel ist, ich denke , Sie meinen wir glauben P BN P B . (da P B = P und N P B = N P )B PBNPBPB=PNPB=NP
Ramprasad
3
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
2
Todas Satz könnte hier relevant sein, da es eine gibt vielleicht in der Lage sein , den Unterschied zwischen falten und N P zum #P Orakel. (Aber ich bin nicht 100% sicher.)PNP#P
Boaz Barak
2
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
1
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:

10

Es ist ein offenes Problem in der Komplexitätstheorie seit vielen Jahren , wenn Zusammenbruch, wobei P H die Polynomialzeit - Hierarchie ist. Es ist auch ein offenes Problem, ein Orakel zu konstruieren, um P # P von P S P A C E zu trennen .PH#PPHP#PPSPACE

Bin Fu
quelle
2
Willkommen bei CSTheory.SE, @Bin Fu! :)
Daniel Apon
Oder vielleicht waren Sie schon einmal hier, aber trotzdem willkommen! ;)
Daniel Apon
1
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? PH#P
Neophyt
1

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

Wenn ich es nicht falsch interpretiere. Satz 4.1 (ii) sagt , " " und c o N P C K = C K .NPCK=CKcoNPCK=CK

Lemma 3.4 (c) sagen : "Für jeden in Zählen Hierarchie, K K C K C K C K ".KKKCKCKCK

Ersetzen von P , erhalten wir P P P P P P .KPPPPPPP

Was bedeutet , .P#PNP#PcoNP#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=NP=coNPP#P=NP#P=coNP#P. If the counting hierarchy collapses, then CCP=CP, i.e. PPPP=PP. By lemma 3.4(c), KKCK, so P#PNP#PcoNP#PNP#PcoNP#PPPPP=PP=P#P, which means in this formula should be = instead.
Mike Chen
1
“The polynomial hierarchy collapses” does not necessarily mean P=NP, and “the counting hierarchy collapses” does not necessarily mean PP=PP^PP.
Tsuyoshi Ito
2
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