Consequências de NP = PSPACE

Quais seriam as conseqüências desagradáveis ​​de NP = PSPACE? Estou surpreso por não ter encontrado nada sobre isso, uma vez que essas aulas estão entre as mais famosas.

Em particular, isso teria alguma conseqüência sobre as classes mais baixas?

Se , isso implicaria:$\mathsf{NP} = \mathsf{PSPACE}$

• $\mathsf{P^{\#P}} = \mathsf{NP}$
  Ou seja, contar as soluções para um problema em seria redutível em polytime para encontrar uma solução única;$\mathsf{NP}$

• $\mathsf{PP} = \mathsf{NP}$
  Ou seja, algoritmos aleatórios em tempo polinomial com probabilidade de sucesso arbitrariamente próximos a 1/2 são reduzidos em tempo polinomial a algoritmos aleatórios em tempo polinomial com erro unilateral, onde instâncias YES são aceitas com probabilidade arbitrariamente pequena;

• $\mathsf{MA} = \mathsf{NP}$
  Ou seja, para qualquer problema verificável em tempo polinomial, a randomização fornece, na melhor das hipóteses, uma aceleração em tempo polinomial (mas esse é apenas um corolário do colapso da hierarquia de tempo polinomial);

• $\mathsf{BQP} \subseteq \mathsf{NP}$
  Ou seja, qualquer problema solucionável por um computador quântico verifica facilmente certificados para suas respostas; isso seria um resultado positivo importante na filosofia da mecânica quântica e provavelmente seria útil no esforço de construir computadores quânticos (para verificar se eles estão fazendo o que deveriam).

Tudo isso se deve às contenções das classes do lado esquerdo no (embora também tenhamos ).B Q P ⊆ P $\mathsf{PSPACE}$$\mathsf{BQP \subseteq PP}$

Um ponto que tem sido implicitamente, mas não explicitamente mencionado ainda é que obteríamos . Embora isso seja equivalente a P H colapsar com N P , decorre diretamente do fato de P S P A C E ser fechado sob complemento, o que é trivial de provar.$\mathsf{NP} = \mathsf{coNP}$$\mathsf{PH}$$\mathsf{NP}$$\mathsf{PSPACE}$

Eu acho que vale a pena apontar por conta do grande número de conseqüências surpreendentes que tem: existem provas curtas que testemunham quando um gráfico não é tricolor, * não-* hamiltoniano, quando dois gráficos são * não- * isomórficos, ... e (em certo sentido de maneira mais geral) que existe algum sistema de prova de Cook-Reckhow no qual toda tautologia proposicional tem uma prova de tamanho polinomial.$\mathsf{NP} = \mathsf{coNP}$

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

1) polinomial Hierarquia entraria em colapso para .${\bf NP }$

2) Agora teremos pois sabemos que P S P A C E ≠ N ${\bf NP } \not ={\bf NL}$${\bf PSPACE} \not = {\bf NL}$

---ATUALIZAR---

3) É sabido que a , onde eles são o espaço delimitado logarítmica versões de N P , C = P e P P respectivamente. Em seguida, por definição, nenhuma dessas classes de complexidade pode ser igual N P sob a suposição 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}$