Quelles seraient les conséquences de PH = PSPACE?

Une question récente (voir les conséquences de NP = PSPACE ) a demandé des conséquences "désagréables" de . Les réponses liste assez peu de conséquences de l' effondrement, y compris et d' autres, en fournissant beaucoup de raisons de croire . $NP=PSPACE$ $NP=coNP$ $NP\neq PSPACE$

Quelles seraient les conséquences de l'effondrement un peu moins dramatique ? $PH=PSPACE$

cc.complexity-theory complexity-classes conditional-results Andras Farago
la source

Suis-je la seule personne à s'ennuyer avec la vague de questions "Conséquences de

" de nos jours? Certes, elles peuvent conduire à des réponses intéressantes, mais la question devrait au moins demander des conséquences inattendues , surprenantes , etc.

A = B

$A=B$

Sylvain

@Sylvain: certaines de ces questions sont en fait de vieilles questions qui sont ressuscitées des morts parce que je leur ai ajouté la balise "conditional-results". Vous pouvez ensuite choisir d'ignorer cette balise pour rendre ces questions moins visibles pour vous.

András Salamon

Réponses:

s'effondre. A problème -complete doit être danscertain niveau de , dire qu'il est dans . Depuis sa -complete -complete (par hypothèse), . $\mathsf{PH}$ $\mathsf{PSPACE}$ $\mathsf{PH}$ $\mathsf{\Sigma_k P}$ $\mathsf{PSPACE}$ $=\mathsf{PH}$ $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$

Joshua Grochow
la source

n'est-il pas fermé sous complément et bas pour lui-même? C'est-à-dire

Donc, cela n'implique-t-il pas

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:

$\:$ Je ne vois pas comment une telle implication pourrait être montrée.

$\;\;\;\;$

@TayfunPay: Notez que

- lorsqu'il est considéré comme la classe unique définie par l'alternance de poly-temps TM avec

alternations - est également fermé sous complément et auto-bas (même sans supposer qu'il est égal à

P H

$\mathsf{PH}$

O (1)

$O(1)$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

@JoshuaGrochow L'existence d'un PH-Complete n'implique-t-elle pas que

s'effondre? Je me souviens de quelque chose comme ça dans l'ancien livre de Papadimitriou. Je vais le vérifier ce soir.

P H

${\bf PH}$

Tayfun Pay du

@TayfunPay: Oui, en utilisant la même preuve que dans ma réponse (mais cela ne dit pas, et apparemment ne peut pas, à quel niveau il s'effondre sous cette hypothèse).

Joshua Grochow

Cela impliquerait encore des séparations majeures des classes de complexité. Par exemple, suivrait. (Si alors ) $\mathrm{LOGSPACE \neq NP}$ $\mathrm{LOGSPACE = NP}$ $\mathrm{LOGSPACE = PH}$

De même, impliquerait par Karp-Lipton. Il s'ensuit que a des circuits polysize si et seulement si fait. Et bien sûr, nous aurions ssi . Dans tous les cas, les conséquences de la résolution de $\mathrm{NP \subseteq P/poly}$ $\mathrm{PSPACE = \Sigma_2 P}$ $\mathrm{NP}$ $\mathrm{PSPACE}$ $\mathrm{P = NP}$ $\mathrm{P = PSPACE}$ $\mathrm{NP}$ efficacement les problèmes seraient considérablement accrus.

Ryan Williams
la source

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
la source