Was wären die Konsequenzen von PH = PSPACE?

13

In einer kürzlich gestellten Frage (siehe Konsequenzen von NP = PSPACE ) wurden die "schlimmen" Konsequenzen von erfragt . Die Antworten Liste nicht wenige Zusammenbruch Folgen, einschließlich N P = c o N P und andere, viel von Gründen zu glauben , N P P S P A C E .NP=PSPACENP=coNPNPPSPACE

Was wären die Folgen des etwas weniger dramatischen Zusammenbruchs ?PH=PSPACE

Andras Farago
quelle
10
Bin ich die einzige Person, die heutzutage gelangweilt von der Welle der "Folgen von " -Fragen ist? Zugegeben, sie können zu interessanten Antworten führen, aber die Frage sollte zumindest unerwartete , überraschende usw. Konsequenzen haben. A=B
Sylvain
2
@ Sylvain: Einige davon sind tatsächlich alte Fragen, die von den Toten auferstanden sind, weil ich ihnen das Tag "conditional-results" hinzugefügt habe. Sie können dieses Tag dann ignorieren, um solche Fragen für Sie weniger sichtbar zu machen.
András Salamon

Antworten:

20

zusammenbricht. A P S P A C E -komplette Problem ingewissen Maß an sein muss P H , sagendass es in ist Σ k P . Da es sich um P S P A C E -komplette = P H -komplette (durch Annahme), P H& Sigma; k P .PHPSPACEPHΣkPPSPACE=PHPHΣkP

Joshua Grochow
quelle
Ist nicht für sich selbst komplementär und niedrig geschlossen? Das ist P S P A C E = P S P A C E P S P A C E So würde das nicht bedeuten , dass N P = C o N P und N P = P S P A C E ? PSPACEPSPACEPSPACEPSPACENP=CoNPNP=PSPACE
Tayfun Pay
@TayfunPay: Ich sehe nicht ein, wie eine solche Implikation gezeigt werden könnte.
1
@TayfunPay: Man beachte , daß - wenn sie als das einzige Klasse definiert durch alternierende Poly Zeit TMs als mit O ( 1 ) Wechsel - unter Ergänzung und selbst niedrig ist auch (noch geschlossen ist es gleich , ohne unter der Annahme P S P A C E ). PHO(1)PSPACE
Joshua Grochow
@JoshuaGrochow nicht die Existenz eines PH-Complete bedeuten , dass zusammenbricht? Ich erinnere mich an so etwas im alten Papadimitriou-Buch. Ich werde es heute Abend überprüfen. PH
Tayfun Pay
1
@TayfunPay: Ja, ich verwende den gleichen Beweis wie in meiner Antwort (aber das kann und kann anscheinend nicht sagen, auf welche Ebene es unter dieser Annahme zusammenbricht).
Joshua Grochow
19

Es würde immer noch bedeutende Trennungen von Komplexitätsklassen bedeuten. Zum Beispiel würde folgen. (Wenn L O G S P A C E = N P, dann L O G S P A C E = P H. )LOGSPACENPLOGSPACE=NPLOGSPACE=PH

Auch würde bedeuten , P S P A C E = Σ 2 P von Karp-Lipton. Daraus folgt, dass N P genau dann Polysize-Schaltungen hat, wenn P S P A C E dies tut. Und natürlich hätten wir P = N P genau dann , wenn P = P S P A C E . In jedem Fall sind die Folgen der Lösung von N PNPP/polyPSPACE=Σ2PNPPSPACEP=NPP=PSPACENP Probleme effizient würde deutlich erhöht.

Ryan Williams
quelle
In der Tat folgt sogar NL ≠ NP , weil . NPNLcoNL=NP
Domotorp
2

PH=PSPACENP=PSPACE

NPPHNP=PHPH=PSPACENP=PSPACENPPH (was wiederum äquivalent ist zu NPcÖNP).

Andras Farago
quelle