<p>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. </p>

<p>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 <em>not</em> 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 <em>every</em> propositional tautology has a polynomial-sized proof.</p>

CC BY-SA 3.0
2014-02-14T01:06:47.970Z
2014-02-14T01:06:47.970Z
Joshua Grochow
<p>If ${\bf NP} = {\bf PSPACE}$</p>

<p>1) Polynomial Hierarchy would collapse to ${\bf NP }$.</p>

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

<p>---UPDATE---</p>

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

CC BY-SA 3.0
2014-02-13T19:44:34.767Z
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.
Denis
CC BY-SA 3.0
2014-02-13T20:25:16.117Z
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).
Niel de Beaudrap
CC BY-SA 3.0
2014-02-13T22:15:51.013Z
@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}$.
Tayfun Pay
CC BY-SA 3.0
2014-02-13T22:19:12.493Z
@dkuper see https://www.math.ucdavis.edu/~greg/zoology/diagram.xml
Tayfun Pay
CC BY-SA 3.0
2014-02-14T00:45:17.850Z
@TayfunPay: (1) why don't you edit your answer to include the relationships from your comment? (2) How do they hold?
Niel de Beaudrap
CC BY-SA 3.0
2014-02-14T01:51:18.790Z
@NieldeBeaudrap I just did! :)
Tayfun Pay
CC BY-SA 3.0
2014-02-13T19:28:42.757Z
2014-02-14T01:49:37.580Z
2014-02-14T01:49:37.580Z
Tayfun Pay
<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2014-02-14T10:10:18.677Z
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.
Denis
CC BY-SA 3.0
2014-02-14T10:38:30.660Z
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.
Alex Grilo
CC BY-SA 3.0
2014-02-14T13:54:12.823Z
@AlexGrilo: hence my comment under the question :)
Alessandro Cosentino
CC BY-SA 3.0
2014-02-14T14:43:40.017Z
@AlessandroCosentino Sorry, I didn't see it before
Alex Grilo
CC BY-SA 3.0
2014-02-14T02:01:22.310Z
2014-02-14T20:20:35.293Z
2014-02-14T20:20:35.293Z
Alex Grilo
<p>If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply:</p>

<ul>
<li><p>$\mathsf{P^{\#P}} = \mathsf{NP}$<br>That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single solution;</p></li>
<li><p>$\mathsf{PP} = \mathsf{NP}$<br>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;</p></li>
<li><p>$\mathsf{MA} = \mathsf{NP}$<br>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);</p></li>
<li><p>$\mathsf{BQP} \subseteq \mathsf{NP}$<br>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).</p></li>
</ul>

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

CC BY-SA 3.0
2014-02-13T22:23:15.887Z
Can you point to a reference where ${\bf NP} = {\bf PSPACE}$ implies that ${\bf BQP} \subseteq {\bf NP}$. Thanks
Tayfun Pay
CC BY-SA 3.0
2014-02-13T23:24:49.390Z
@TayfunPay You basically want a reference for $\mathsf{BQP} \subseteq \mathsf{PSPACE}$. The reference for that is [BV97](https://complexityzoo.uwaterloo.ca/Zooref#bv97). However, you can also prove that $\mathsf{BQP} \subseteq \mathsf{PP}$. See the following lecture for intuition on this: http://www.scottaaronson.com/democritus/lec10.html
Alessandro Cosentino
CC BY-SA 3.0
2014-02-13T23:58:14.827Z
@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! :)
Tayfun Pay
CC BY-SA 3.0
2014-02-13T20:02:13.723Z
2014-02-14T00:46:43.713Z
2014-02-14T00:46:43.713Z
Niel de Beaudrap
<p>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.</p>

<p>In particular, would it have any consequences on the lower classes?</p>

CC BY-SA 3.0
2014-02-13T23:44:14.133Z
An immediate corollary, or rather a reformulation of the identity: the verifier wouldn't need to message back the prover, ever!
Alessandro Cosentino
<cc.complexity-theory><complexity-classes><conditional-results>
Consequences of NP=PSPACE
Denis
# Consequences of NP=PSPACE

(Asked by: username_0 on 2014-02-13)

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?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results
> **Comments:**
> **username_1**: An immediate corollary, or rather a reformulation of the identity: the verifier wouldn't need to message back the prover, ever!  

---

## 4 answers

### Answer by username_4 on 2014-02-13. Score: 28 | Accepted answer

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

> **Comments:**
> **username_3**: Can you point to a reference where ${\bf NP} = {\bf PSPACE}$ implies that ${\bf BQP} \subseteq {\bf NP}$. Thanks  
> **username_1**: @TayfunPay You basically want a reference for $\mathsf{BQP} \subseteq \mathsf{PSPACE}$. The reference for that is [BV97](https://complexityzoo.uwaterloo.ca/Zooref#bv97). However, you can also prove that $\mathsf{BQP} \subseteq \mathsf{PP}$. See the following lecture for intuition on this: http://www.scottaaronson.com/democritus/lec10.html  
> **username_3**: @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! :)  

---

### Answer by username_2 on 2014-02-14. Score: 22

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 by username_3 on 2014-02-13. Score: 12

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

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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).  
> **username_3**: @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}$.  
> **username_3**: @dkuper see https://www.math.ucdavis.edu/~greg/zoology/diagram.xml  
> **username_4**: @TayfunPay: (1) why don't you edit your answer to include the relationships from your comment? (2) How do they hold?  
> **username_3**: @NieldeBeaudrap I just did! :)  

---

### Answer by username_5 on 2014-02-14. Score: 10

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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: 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.  
> **username_1**: @AlexGrilo: hence my comment under the question :)  
> **username_5**: @AlessandroCosentino Sorry, I didn't see it before  

---

