Jakie byłyby konsekwencje PH = PSPACE?

Ostatnie pytanie (patrz Konsekwencje NP = PSPACE ) dotyczyło „paskudnych” konsekwencji . W odpowiedziach wymieniono kilka skutków zawalenia, w tym i inne, dostarczając wielu powodów, aby wierzyć . $NP=PSPACE$ $NP=coNP$ $NP\neq PSPACE$

Jakie byłyby konsekwencje nieco mniej dramatycznego załamania ? $PH=PSPACE$

cc.complexity-theory complexity-classes conditional-results Andras Farago
źródło

Czy w dzisiejszych czasach jestem jedyną osobą znudzoną falą pytań „Konsekwencje ”? To prawda, że mogą prowadzić do interesujących odpowiedzi, ale pytanie powinno przynajmniej prosić o nieoczekiwane , zaskakujące itp. Konsekwencje.

A = B

$A=B$

Sylvain

@Sylvain: niektóre z nich są tak naprawdę starymi pytaniami, które powstały z martwych, ponieważ dodałem do nich znacznik „wyniki warunkowe”. Następnie możesz zignorować ten tag, aby takie pytania były dla Ciebie mniej widoczne.

András Salamon

Odpowiedzi:

$\mathsf{PH}$ upada. -Complete problem musi być w pewnym poziomie , powiedzieć, że jest w . Ponieważ jest to -complete -complete (z założenia), . $\mathsf{PSPACE}$ $\mathsf{PH}$ $\mathsf{\Sigma_k P}$ $\mathsf{PSPACE}$ $=\mathsf{PH}$ $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$

Joshua Grochow
źródło

Czy zamknięte dla siebie jako uzupełnienie i niskie? To jest = Czy to nie oznaczałoby i ?

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 Zapłać

@TayfunPay: Nie rozumiem, w jaki sposób można wykazać taką implikację.

$\:$

$\;\;\;\;$

@TayfunPay: Zauważ, że - jeśli jest uważany za pojedynczą klasę zdefiniowaną przez naprzemienne wielotaktowe TM z alternatywami - jest również zamknięty w ramach dopełniania i samo-niskiego poziomu (nawet nie zakładając, że jest równy ).

P H

$\mathsf{PH}$

O (1)

$O(1)$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

@JoshuaGrochow Czy istnienie PH-Complete nie oznacza, że zawali? Pamiętam coś takiego w starej książce Papadimitriou. Sprawdzę to dziś wieczorem.

P H

${\bf PH}$

Tayfun Zapłać

@TayfunPay: Tak, używając tego samego dowodu, co w mojej odpowiedzi (ale to nie mówi i najwyraźniej nie może powiedzieć, do jakiego poziomu się zawali przy tym założeniu).

Joshua Grochow

Wciąż oznaczałoby to poważne rozdzielenie klas złożoności. Na przykład . (Jeśli to .) $\mathrm{LOGSPACE \neq NP}$ $\mathrm{LOGSPACE = NP}$ $\mathrm{LOGSPACE = PH}$

Również implikuje autorstwa Karp-Lipton. Wynika z tego, że ma obwody polizowania wtedy i tylko wtedy, gdy ma. I oczywiście mielibyśmy iff . W każdym razie konsekwencje skutecznego rozwiązywania problemów zostałyby znacznie zwiększone. $\mathrm{NP \subseteq P/poly}$ $\mathrm{PSPACE = \Sigma_2 P}$ $\mathrm{NP}$ $\mathrm{PSPACE}$ $\mathrm{P = NP}$ $\mathrm{P = PSPACE}$ $\mathrm{NP}$

Ryan Williams
źródło

W rzeczywistości, nawet NL ≠ NP następuje ponieważ

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

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

domotorp

Ponieważ odpowiedzi podkreślić, wciąż mają znaczące skutki, chociaż nie tak licznych i dramatycznych jak . $PH=PSPACE$ $NP=PSPACE$

Włączanie problem na głowie, to może być postrzegane jako „empirycznych dowodów”, by wesprzeć . W końcu, jeśli , to dwie instrukcje ( i ) muszą mieć takie same konsekwencje. Ponieważ druga hipoteza ma zauważalnie więcej i silniejsze znane konsekwencje, można ją postrzegać jako dowód empiryczny na poparcie tego, że lewa strona równania musi być inna, to znaczy $NP\neq PH$ $NP=PH$ $PH=PSPACE$ $NP=PSPACE$ (co z kolei jest równoważne ). $NP\neq PH$ $NP\neq coNP$

Andras Farago
źródło