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?

  • 4
    $\begingroup$ An immediate corollary, or rather a reformulation of the identity: the verifier wouldn't need to message back the prover, ever! $\endgroup$ – Alessandro Cosentino Feb 13 '14 at 23:44

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}$).

  • 1
    $\begingroup$ Can you point to a reference where ${\bf NP} = {\bf PSPACE}$ implies that ${\bf BQP} \subseteq {\bf NP}$. Thanks $\endgroup$ – Tayfun Pay Feb 13 '14 at 22:23
  • 2
    $\begingroup$ @TayfunPay You basically want a reference for $\mathsf{BQP} \subseteq \mathsf{PSPACE}$. The reference for that is BV97. However, you can also prove that $\mathsf{BQP} \subseteq \mathsf{PP}$. See the following lecture for intuition on this: scottaaronson.com/democritus/lec10.html $\endgroup$ – Alessandro Cosentino Feb 13 '14 at 23:24
  • 2
    $\begingroup$ @AlessandroCosentino Yes, I knew that ${\bf BPP} \subseteq {\bf BQP} \subseteq {\bf PP} \subseteq {\bf PSPACE}$ and that ${\bf NP} \subseteq {\bf PP} \subseteq {\bf PSPACE}$. I guess I just needed to be pointed out to jiggle my memory! Thanks! :) $\endgroup$ – Tayfun Pay Feb 13 '14 at 23:58

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.


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}$


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}$.

  • 1
    $\begingroup$ These are trivial consequences following PH$\subseteq$PSPACE and NL$\neq$PSPACE, I was hoping for more surprising consequences, for instance something between NL and P, or any new relation between two classes "strictly" below NP. $\endgroup$ – Denis Feb 13 '14 at 19:44
  • 1
    $\begingroup$ Note that if you consider NL as the class of languages which have solutions which can be verified in logspace, even if each symbol of the solution is read at most once (albeit where logarithmically many can be stored on the work tape at any one time), the fact that it differs from NP indicates that there is a class L' which is a relative of L, involving Turing Machines with two input tapes but where one is read-once and the other is not, and which is different from P (where because one has polynomial space on the worktape, read-once input limitations don't matter). $\endgroup$ – Niel de Beaudrap Feb 13 '14 at 20:25
  • 1
    $\begingroup$ @dkuper You would also have ${\bf PL} \not = {\bf NP}$, where ${\bf PL}$ is the logarithmic space bounded version of ${\bf PP}$ as well as ${\bf \#L} \not = {\bf NP}$, where ${\bf \#L}$ is the logarithmic space bounded version of ${\bf \#P}$. $\endgroup$ – Tayfun Pay Feb 13 '14 at 22:15
  • 1
    $\begingroup$ @dkuper see math.ucdavis.edu/~greg/zoology/diagram.xml $\endgroup$ – Tayfun Pay Feb 13 '14 at 22:19
  • 1
    $\begingroup$ @TayfunPay: (1) why don't you edit your answer to include the relationships from your comment? (2) How do they hold? $\endgroup$ – Niel de Beaudrap Feb 14 '14 at 0:45

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.

  • $\begingroup$ It could still depend on the implementation though? Meaning there would still be interactive provers needing more exchangse, only there exists others with only one message for the same language. $\endgroup$ – Denis Feb 14 '14 at 10:10
  • $\begingroup$ Well, it would mean that one message is sufficient. If I understood your question correctly, it's the same for problems in P: although there are polynomial time algorithms for them, one can still create an exponential time algorithm. $\endgroup$ – Alex Grilo Feb 14 '14 at 10:38
  • 2
    $\begingroup$ @AlexGrilo: hence my comment under the question :) $\endgroup$ – Alessandro Cosentino Feb 14 '14 at 13:54
  • $\begingroup$ @AlessandroCosentino Sorry, I didn't see it before $\endgroup$ – Alex Grilo Feb 14 '14 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.