Consecuencias de NP = PSPACE

¿Cuáles serían las desagradables consecuencias de NP = PSPACE? Me sorprende no haber encontrado nada sobre esto, dado que estas clases se encuentran entre las más famosas.

En particular, ¿tendría alguna consecuencia en las clases bajas?

Si , esto implicaría:$\mathsf{NP} = \mathsf{PSPACE}$

• Es decir, contar las soluciones a un problema en N P sería politemporalmente reducible para encontrar una solución única;$\mathsf{P^{\#P}} = \mathsf{NP}$
  $\mathsf{NP}$

• Es decir, los algoritmos aleatorios de tiempo polinomial con probabilidad de éxito arbitrariamente cercana a 1/2 son algoritmos aleatorios de tiempo polinomial reducibles a algoritmos aleatorios de tiempo polinomial con error unilateral, donde las instancias SÍ se aceptan con probabilidad arbitrariamente pequeña;$\mathsf{PP} = \mathsf{NP}$
  

• Es decir, para cualquier problema que sea verificable en el tiempo polinomial, la aleatorización proporciona una aceleración del tiempo polinomial en el mejor de los casos (pero esto es solo un corolario del colapso de la jerarquía del tiempo polinomial);$\mathsf{MA} = \mathsf{NP}$
  

• Es decir, cualquier problema que pueda ser resuelto por una computadora cuántica ha verificado fácilmente los certificados de sus respuestas; este sería un resultado positivo importante en la filosofía de la mecánica cuántica, y probablemente sería útil para el esfuerzo de construir computadoras cuánticas (para verificar que están haciendo lo que deben hacer).$\mathsf{BQP} \subseteq \mathsf{NP}$
  

Todo esto se debe a la contención de las clases en el lado izquierdo en (aunque también tenemos B Q P ⊆ P P ).$\mathsf{PSPACE}$$\mathsf{BQP \subseteq PP}$

Un punto que ha sido implícita pero no explícitamente mencionado aún es que nos darían . Aunque esto es equivalente al colapso de P H a N P , se deduce directamente del hecho de que P S P A C E está cerrado bajo el complemento, lo cual es trivial de probar.$\mathsf{NP} = \mathsf{coNP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{PSPACE}$

Creo que vale la pena señalar por sí solo debido a la gran cantidad de consecuencias sorprendentes que tiene: hay pruebas cortas que atestiguan cuando un gráfico no es 3-colorable, * no- * Hamiltoniano, cuando dos gráficos son * no * isomórficos, ..., y (en cierto sentido de manera más general) que hay algún sistema de prueba de Cook-Reckhow en el que cada tautología proposicional tiene una prueba de tamaño polinómico.$\mathsf{NP} = \mathsf{coNP}$

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

1) Polinomio Jerarquía colapsaría a .${\bf NP }$

2) Ahora tendremos que ya que sabemos que P S P A C E ≠ N ${\bf NP } \not ={\bf NL}$${\bf PSPACE} \not = {\bf NL}$

---ACTUALIZAR---

3) Se sabe que , donde están las versiones limitadas en el espacio logarítmico de N P , C = P y P P respectivamente. Entonces, por definición, ninguna de estas clases de complejidad podría ser igual N P bajo el supuesto de 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}$

${\bf IP}$${\bf NP}$

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