31
$\begingroup$

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?

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

4 Answers 4

28
$\begingroup$

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

$\endgroup$
3
  • 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, 2014 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$ Feb 13, 2014 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, 2014 at 23:58
22
$\begingroup$

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.

$\endgroup$
0
12
$\begingroup$

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

$\endgroup$
6
  • 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, 2014 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$ Feb 13, 2014 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, 2014 at 22:15
  • 1
    $\begingroup$ @dkuper see math.ucdavis.edu/~greg/zoology/diagram.xml $\endgroup$
    – Tayfun Pay
    Feb 13, 2014 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$ Feb 14, 2014 at 0:45
10
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2014 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, 2014 at 10:38
  • 2
    $\begingroup$ @AlexGrilo: hence my comment under the question :) $\endgroup$ Feb 14, 2014 at 13:54
  • $\begingroup$ @AlessandroCosentino Sorry, I didn't see it before $\endgroup$
    – Alex Grilo
    Feb 14, 2014 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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