Consequences of NP=PSPACE

Question

What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones.

In particular, would it have any consequences on the lower classes?

Answer 1

If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply:

• $\mathsf{P^{\#P}} = \mathsf{NP}$
  That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single solution;

• $\mathsf{PP} = \mathsf{NP}$
  That is, polynomial-time randomized algorithms with success probability arbitrarily close to 1/2 is polynomial-time reducible to polynomial-time randomized algorithms with one-sided error, where YES instances are accepted with arbitrarily small probability;

• $\mathsf{MA} = \mathsf{NP}$
  That is, for any problem which is verifiable in polynomial time, randomization provides a polynomial-time speedup at best (but this is just a corollary of the polynomial-time hierarchy collapsing);

• $\mathsf{BQP} \subseteq \mathsf{NP}$
  That is, any problem which is solvable by a quantum computer has easily verified certificates for its answers; this would be an important positive result in the philosophy of quantum mechanics, and would probably be helpful to the effort to construct quantum computers (for verifying that they are doing what they are meant to be doing).

All of these are due to containments of the classes on the left-hand sides in $\mathsf{PSPACE}$ (though we also have $\mathsf{BQP \subseteq PP}$).

Answer 2

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.

I think $\mathsf{NP} = \mathsf{coNP}$ is worth pointing out on its own because of the large number of surprising consequences it has: there are short proofs witnessing when a graph is not 3-colorable, *non-*Hamiltonian, when two graphs are *non-*isomorphic, ..., and (in some sense more generally) that there is some Cook-Reckhow proof system in which every propositional tautology has a polynomial-sized proof.

Answer 3

If ${\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}$.

Answer 4

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.