¿Cuáles serían las consecuencias de PH = PSPACE?

Una pregunta reciente (ver Consecuencias de NP = PSPACE ) pidió a las consecuencias "desagradables" de $NP=PSPACE$ . Las respuestas lista bastantes consecuencias de colapso, incluyendo $NP=coNP$ y otros, proporcionando un montón de razones para creer $NP\neq PSPACE$ .

¿Cuáles serían las consecuencias del colapso algo menos dramático ? $PH=PSPACE$

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

¿Soy la única persona aburrida con la oleada de preguntas "Consecuencias de

" en estos días? Por supuesto, pueden conducir a respuestas interesantes, pero la pregunta al menos debería tener consecuencias inesperadas , sorprendentes , etc.

A = B

$A=B$

Sylvain

@Sylvain: algunas de esas son en realidad viejas preguntas que han surgido de entre los muertos porque les agregué la etiqueta "resultados condicionales". Luego puede optar por ignorar esa etiqueta para que esas preguntas sean menos visibles para usted.

András Salamon

Respuestas:

derrumba. A problema -Complete debe estar en algún nivel de , dicen que es en . Puesto que de -Complete -Complete (por supuesto), . $\mathsf{PH}$ $\mathsf{PSPACE}$ $\mathsf{PH}$ $\mathsf{\Sigma_k P}$ $\mathsf{PSPACE}$ $=\mathsf{PH}$ $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$

Joshua Grochow
fuente

¿No está cerrado

bajo complemento y bajo por sí mismo? Eso es

Entonces, ¿eso no implicaría

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 paga

@TayfunPay:

$\:$ No veo cómo podría mostrarse tal implicación.

$\;\;\;\;$

@TayfunPay: Tenga en cuenta que

, cuando se considera como la clase única definida por la alternancia de TM de tiempo múltiple con alternancias

, también se cierra bajo complemento y auto-bajo (incluso sin suponer que es igual a

)

P H

$\mathsf{PH}$

O (1)

$O(1)$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

@JoshuaGrochow ¿La existencia de un PH-Complete no implica que se derrumbe

? Recuerdo algo como esto en el viejo libro de Papadimitriou. Lo comprobaré esta noche.

P H

${\bf PH}$

Tayfun paga

@TayfunPay: Sí, usando la misma prueba que en mi respuesta (pero eso no, y aparentemente no puede decir a qué nivel se colapsa bajo esa suposición).

Joshua Grochow

Todavía implicaría separaciones importantes de clases de complejidad. Por ejemplo, seguiría. (Si entonces $\mathrm{LOGSPACE \neq NP}$ $\mathrm{LOGSPACE = NP}$ $\mathrm{LOGSPACE = PH}$ )

También implicaría por Karp-Lipton. Se deduce que tiene circuitos de polisización si y solo si tiene. Y, por supuesto, tendríamos si y sólo si . En cualquier caso, las consecuencias de resolver $\mathrm{NP \subseteq P/poly}$ $\mathrm{PSPACE = \Sigma_2 P}$ $\mathrm{NP}$ $\mathrm{PSPACE}$ $\mathrm{P = NP}$ $\mathrm{P = PSPACE}$ $\mathrm{NP}$ Los problemas se aumentarían de manera eficiente.

Ryan Williams
fuente

In fact, even NL≠NP follows because

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

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

domotorp

As the answers point out, $PH=PSPACE$ would still have significant consequences, even though not as numerous and dramatic ones as $NP=PSPACE$ .

Turning the issue on its head, it could be viewed as "empirical evidence" to support $NP\neq PH$ . After all, if $NP=PH$ , then the two statements ( $PH=PSPACE$ and $NP=PSPACE$ ) must have the same consequences. As the second hypothesis has noticeably more and stronger known consequences, that can be viewed as empirical evidence to support that the left-hand sides in the equations must be different, that is $NP\neq PH$ (which, in turn, is equivalent to $NP\neq coNP$ ).

Andras Farago
fuente