Was wären die Konsequenzen von PH = PSPACE?

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 und andere, viel von Gründen zu glauben , . $NP=PSPACE$ $NP=coNP$ $NP\neq PSPACE$

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

cc.complexity-theory complexity-classes conditional-results Andras Farago
quelle

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

$A=B$

Sylvain

@ 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:

zusammenbricht. A -komplette Problem ingewissen Maß an sein muss , sagendass es in ist . Da es sich -komplette -komplette (durch Annahme), . $\mathsf{PH}$ $\mathsf{PSPACE}$ $\mathsf{PH}$ $\mathsf{\Sigma_k P}$ $\mathsf{PSPACE}$ $=\mathsf{PH}$ $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$

Joshua Grochow
quelle

Ist

nicht für sich selbst komplementär und niedrig geschlossen? Das ist

So würde das nicht bedeuten , dass

und

P S P A C E

${\bf PSPACE}$

P S P A C E

${\bf PSPACE}$

{P S P A C E}^{P S P A C E}

${\bf PSPACE}^{\bf PSPACE}$

N P = C o N P

${\bf NP} = {\bf CoNP}$

N P = P S P A C E

${\bf NP} ={\bf PSPACE}$

Tayfun Pay

@TayfunPay:

$\:$ Ich sehe nicht ein, wie eine solche Implikation gezeigt werden könnte.

$\;\;\;\;$

@TayfunPay: Man beachte , daß

- wenn sie als das einzige Klasse definiert durch alternierende Poly Zeit TMs als mit

Wechsel - unter Ergänzung und selbst niedrig ist auch (noch geschlossen ist es gleich , ohne unter der Annahme

P H

$\mathsf{PH}$

O (1)

$O(1)$

P S P A C E

$\mathsf{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.

P H

${\bf PH}$

Tayfun Pay

@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

Es würde immer noch bedeutende Trennungen von Komplexitätsklassen bedeuten. Zum Beispiel würde folgen. (Wenn dann ) $\mathrm{LOGSPACE \neq NP}$ $\mathrm{LOGSPACE = NP}$ $\mathrm{LOGSPACE = PH}$

Auch würde bedeuten , von Karp-Lipton. Daraus folgt, dass genau dann Polysize-Schaltungen hat, wenn tut. Und natürlich hätten wir genau dann , wenn . In jedem Fall sind die Folgen der Lösung von $\mathrm{NP \subseteq P/poly}$ $\mathrm{PSPACE = \Sigma_2 P}$ $\mathrm{NP}$ $\mathrm{PSPACE}$ $\mathrm{P = NP}$ $\mathrm{P = PSPACE}$ $\mathrm{NP}$ Probleme effizient würde deutlich erhöht.

Ryan Williams
quelle

In der Tat folgt sogar NL ≠ NP , weil

N P^{N L \cap c o - N L} = N P

$NP^{NL\cap co-NL}=NP$

Domotorp

$PH=PSPACE$ $NP=PSPACE$

$NP\neq PH$ $NP=PH$ $PH=PSPACE$ $NP=PSPACE$ $NP\neq PH$ (was wiederum äquivalent ist zu $NP\neq coNP$ ).

Andras Farago
quelle