Conséquences de NP = PSPACE

Quelles seraient les conséquences désagréables de NP = PSPACE? Je suis surpris de n'avoir rien trouvé à ce sujet, étant donné que ces cours sont parmi les plus célèbres.

En particulier, cela aurait-il des conséquences sur les classes inférieures?

Si $\mathsf{NP} = \mathsf{PSPACE}$ , cela impliquerait:

• $\mathsf{P^{\#P}} = \mathsf{NP}$
  Autrement dit, compter les solutions à un problème dans$\mathsf{NP}$ serait polytemporaire réductible à la recherche d'une solution unique;

• $\mathsf{PP} = \mathsf{NP}$
  Autrement dit, les algorithmes randomisés en temps polynomial avec une probabilité de réussite arbitrairement proche de 1/2 sont réductibles en temps polynomial en algorithmes randomisés en temps polynomial avec erreur unilatérale, où les instances YES sont acceptées avec une probabilité arbitrairement petite;

• C'est-à-dire que pour tout problème vérifiable en temps polynomial, la randomisation fournit au mieux une accélération polynomiale (mais ce n'est qu'un corollaire de l'effondrement de la hiérarchie polynomiale);$\mathsf{MA} = \mathsf{NP}$
  

• C'est-à-dire que tout problème qui peut être résolu par un ordinateur quantique a facilement vérifié les certificats pour ses réponses; ce serait un résultat positif important dans la philosophie de la mécanique quantique, et serait probablement utile aux efforts de construction d'ordinateurs quantiques (pour vérifier qu'ils font ce qu'ils sont censés faire).$\mathsf{BQP} \subseteq \mathsf{NP}$
  

Tout cela est dû aux confinements des classes sur le côté gauche dans (bien que nous ayons également B Q P ⊆ P P ).$\mathsf{PSPACE}$$\mathsf{BQP \subseteq PP}$

Un point qui a été implicitement mais pas encore explicitement mentionné est que nous obtiendrions . Bien que cela soit équivalent à P H s'effondrant en N P , cela découle directement du fait que P S P A C E est fermé sous complément, ce qui est trivial à prouver.$\mathsf{NP} = \mathsf{coNP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{PSPACE}$

Je pense que mérite d'être souligné à lui seul en raison du grand nombre de conséquences surprenantes qu'il a: il existe de courtes preuves témoignant lorsqu'un graphique n'est pas tricolore, sont * non * isomorphes, ..., et (dans un certain sens plus généralement) qu'il existe un système de preuve Cook-Reckhow dans lequel chaque tautologie propositionnelle a une preuve de taille polynomiale.$\mathsf{NP} = \mathsf{coNP}$

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

1) Polynomial Hierarchy tomberait à .${\bf NP }$

2) Nous aurons maintenant que puisque nous savons que P S P A C E ≠ N ${\bf NP } \not ={\bf NL}$${\bf PSPACE} \not = {\bf NL}$

---MISE À JOUR---

3) On sait que , où ce sont les versions bornées dans l'espace logarithmique de N P , C = P et P P respectivement. Puis , par définition , aucune de ces classes de complexité pourrait être égale N P en supposant que N P = P S P A C E .${\bf NL} \subseteq {\bf C_=L} \subseteq {\bf PL}$${\bf NP}$${\bf C_=P}$${\bf PP}$${\bf NP}$${\bf NP} = {\bf PSPACE}$

En plus des résultats indiqués dans toutes les autres réponses, il y en a un impliquant les systèmes de preuve interactifs ( ), qui sont la généralisation N P où le vérificateur et le prouveur échangent des messages afin de reconnaître une langue.${\bf IP}$${\bf NP}$

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