Konsekwencje NP = PSPACE

Jakie byłyby paskudne konsekwencje NP = PSPACE? Dziwi mnie, że nie znalazłem nic na ten temat, biorąc pod uwagę, że zajęcia te należą do najbardziej znanych.

W szczególności, czy miałoby to jakiekolwiek konsekwencje dla klas niższych?

Jeżeli , oznacza to:$\mathsf{NP} = \mathsf{PSPACE}$

• Oznacza to, że zliczanie rozwiązań problemu w N P byłoby polimeime sprowadzające się do znalezienia jednego rozwiązania;$\mathsf{P^{\#P}} = \mathsf{NP}$
  $\mathsf{NP}$

• To znaczy, że algorytmy randomizowane w czasie wielomianowym z prawdopodobieństwem sukcesu arbitralnie zbliżone do 1/2 są redukowane w czasie wielomianowym do algorytmów losowych w czasie wielomianowym z jednostronnym błędem, gdzie wystąpienia TAK są przyjmowane z arbitralnie małym prawdopodobieństwem;$\mathsf{PP} = \mathsf{NP}$
  

• Oznacza to, że dla każdego problemu, który można zweryfikować w czasie wielomianowym, randomizacja zapewnia co najwyżej przyspieszenie czasu wielomianowego (ale jest to tylko następstwem załamania się hierarchii czasu wielomianowego);$\mathsf{MA} = \mathsf{NP}$
  

• Oznacza to, że każdy problem rozwiązany przez komputer kwantowy łatwo weryfikuje certyfikaty pod kątem odpowiedzi; byłby to ważny pozytywny wynik w filozofii mechaniki kwantowej i prawdopodobnie byłby pomocny w wysiłku budowy komputerów kwantowych (dla weryfikacji, że robią to, co powinni).$\mathsf{BQP} \subseteq \mathsf{NP}$
  

Wszystko to wynika z zamkniętych klas po lewej stronie w (chociaż mamy też B Q P ⊆ P P ).$\mathsf{PSPACE}$$\mathsf{BQP \subseteq PP}$

One point which has been implicitly but not explicitly mentioned yet is that we would get $\mathsf{NP} = \mathsf{coNP}$. Although this is equivalent to $\mathsf{PH}$ collapsing to $\mathsf{NP}$, it follows directly from the fact that $\mathsf{PSPACE}$ is closed under complement, which is trivial to prove.

Myślę, że jest warta uwagi sama z powodu dużej liczby zaskakujących konsekwencji, jakie ma: istnieją krótkie dowody świadczące o tym, że wykres nie jest trójkolorowy, * nie * hamiltonian, gdy dwa wykresy są * nie- * izomorficzne, ... i (w pewnym sensie bardziej ogólnie), że istnieje system dowodu Cook-Reckhow, w którym każda tautologia zdań ma dowód wielomianowy.$\mathsf{NP} = \mathsf{coNP}$

Jeśli ${\bf NP} = {\bf PSPACE}$

1) Polynomial Hierarchy would collapse to ${\bf NP }$.

2) We will now have that ${\bf NP } \not ={\bf NL}$ since we know that ${\bf PSPACE} \not = {\bf NL}$

---UPDATE---

3) It is known that ${\bf NL} \subseteq {\bf C_=L} \subseteq {\bf PL}$, where they are the logarithmic space bounded versions of ${\bf NP}$, ${\bf C_=P}$ and ${\bf PP}$ respectively. Then by definition none of these complexity classes could be equal ${\bf NP}$ under the assumption that ${\bf NP} = {\bf PSPACE}$.

In addition to the results pointed in all other answers, there is a one involving Interactive Proof Systems (${\bf IP}$), that are the generalization ${\bf NP}$ where Verifier and Prover exchange messages in order to recognize a language.

It is known that ${\bf IP = PSPACE}$, so if ${\bf NP = PSPACE}$, it means that only one message is sufficient! For me the more impressing of this result is that the Verifier wouldn't need to challenge the Prover and can trust the very first message sent by her.