<p>No.  It is possible (as far as we know) that $\textbf{P} = \textbf{NP} = \textbf{PSPACE}$.</p>

<p>If $\textbf{P} = \textbf{NP}$, the <a href="https://en.wikipedia.org/wiki/Polynomial_hierarchy" rel="noreferrer">polynomial hierarchy</a> collapses, i.e., $\textbf{P} = \textbf{PH}$.  See also <a href="https://cstheory.stackexchange.com/q/5463/5038">Can one amplify P=NP beyond P=PH?</a> for an attempt to understand the limits of the implications of $\textbf{P} = \textbf{NP}$, and see <a href="https://cstheory.stackexchange.com/q/5399/5038">Why doesn&#39;t P=NP imply P=AP (i.e. P=PSPACE)?</a> for information about why it seems hard to derive the implication $\textbf{P} = \textbf{PSPACE}$.</p>

CC BY-SA 3.0
2017-05-22T22:34:38.437Z
Note that also, $P = PSPACE$ implies that $NL \ne P$ since $NL \ne PSPACE$ ($NL \subseteq SPACE((\log n)^2) \subsetneq PSPACE$ by Savitch's theorem and the space hierarchy theorem).
Mikhail Rudoy
CC BY-SA 3.0
2017-05-22T22:30:05.513Z
2017-05-22T22:30:05.513Z
D.W.
<p>Does $\textbf{P} = \textbf {NP}$ imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for a slightly stronger result, does it imply that $\textbf{NL} = \textbf P$?</p>

CC BY-SA 3.0
2017-05-23T16:04:31.063Z
FWIW, the answer to original question was "yes" while the answer to the edited question is "no" (as far as we know; as explained by D.W.'s answer). They don't ask the same thing.
Huck Bennett
CC BY-SA 3.0
2017-05-23T16:15:19.157Z
@HuckBennett D.W. explained that P=NP and reachability being NP-complete are iff, and I agree. If P=NP, reachability is trivially NP-complete.
Columbo
CC BY-SA 3.0
2017-05-23T17:04:13.833Z
No, he did not and what you said isn't right. Directed s-t connectivity is NL-complete, and P = NP does not (is not known to) imply that NL = NP. (I just wanted to clarify this in case anyone looks at previous versions of the question.)
Huck Bennett
CC BY-SA 3.0
2017-05-23T17:44:26.543Z
@HuckBennett What I said is right. Reachability is in P, hence NP-completeness implies P=NP. P=NP implies that any problem in P is NP-complete.
Columbo
CC BY-SA 3.0
2017-05-23T18:52:12.140Z
Yes, I see, you're right about that. My point is about the difference between P = NP and NL = NP though (which affects the answer to your question).
Huck Bennett
CC BY-SA 3.0
2017-05-27T08:20:29.377Z
@HuckBennett Elaborate, please. Are you saying that reachability being NP-complete does imply NP!=PSPACE?
Columbo
CC BY-SA 3.0
2017-05-27T22:02:16.703Z
Yes, then we would have $NP = NL \neq PSPACE$, where $NL \neq PSPACE$ holds for the reason mentioned in Mikhail Rudoy's comment below.
Huck Bennett
CC BY-SA 3.0
2017-05-27T22:04:40.510Z
@HuckBennett I don't [think so](https://cs.stackexchange.com/a/75942/22754). Or perhaps we're talking past each other.
Columbo
CC BY-SA 3.0
2017-05-27T23:02:03.883Z
Sorry, you're right again. The issue is that an NL-complete language being NP-complete doesn't imply that NL = NP since completeness is defined under different types of reductions for the two classes.
Huck Bennett
CC BY-SA 3.0
2017-05-28T17:39:43.383Z
Yes, it does. This is a corollary to my proof of $\textbf{P}\ne\textbf{NP}$, which unfortunately does not fit into this comment.
Carsten S
<np-hardness><pspace>
Does P = NP imply NP being a strict subset of PSPACE?
Columbo
# Does P = NP imply NP being a strict subset of PSPACE?

(Asked by: username_0 on 2017-05-22)

Does $\textbf{P} = \textbf {NP}$ imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for a slightly stronger result, does it imply that $\textbf{NL} = \textbf P$?

**Tags:** np-hardness, pspace
> **Comments:**
> **username_1**: FWIW, the answer to original question was "yes" while the answer to the edited question is "no" (as far as we know; as explained by D.W.'s answer). They don't ask the same thing.  
> **username_0**: @HuckBennett D.W. explained that P=NP and reachability being NP-complete are iff, and I agree. If P=NP, reachability is trivially NP-complete.  
> **username_1**: No, he did not and what you said isn't right. Directed s-t connectivity is NL-complete, and P = NP does not (is not known to) imply that NL = NP. (I just wanted to clarify this in case anyone looks at previous versions of the question.)  
> **username_0**: @HuckBennett What I said is right. Reachability is in P, hence NP-completeness implies P=NP. P=NP implies that any problem in P is NP-complete.  
> **username_1**: Yes, I see, you're right about that. My point is about the difference between P = NP and NL = NP though (which affects the answer to your question).  
> **username_0**: @HuckBennett Elaborate, please. Are you saying that reachability being NP-complete does imply NP!=PSPACE?  
> **username_1**: Yes, then we would have $NP = NL \neq PSPACE$, where $NL \neq PSPACE$ holds for the reason mentioned in Mikhail Rudoy's comment below.  
> **username_0**: @HuckBennett I don't [think so](https://cs.stackexchange.com/a/75942/22754). Or perhaps we're talking past each other.  
> **username_1**: Sorry, you're right again. The issue is that an NL-complete language being NP-complete doesn't imply that NL = NP since completeness is defined under different types of reductions for the two classes.  
> **username_2**: Yes, it does. This is a corollary to my proof of $\textbf{P}\ne\textbf{NP}$, which unfortunately does not fit into this comment.  

---

## 1 answers

### Answer by username_3 on 2017-05-22. Score: 13 | Accepted answer

No. It is possible (as far as we know) that $\textbf{P} = \textbf{NP} = \textbf{PSPACE}$.

If $\textbf{P} = \textbf{NP}$, the [polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy) collapses, i.e., $\textbf{P} = \textbf{PH}$. See also [Can one amplify P=NP beyond P=PH?](https://cstheory.stackexchange.com/q/5463/5038) for an attempt to understand the limits of the implications of $\textbf{P} = \textbf{NP}$, and see [Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?](https://cstheory.stackexchange.com/q/5399/5038) for information about why it seems hard to derive the implication $\textbf{P} = \textbf{PSPACE}$.

> **Comments:**
> **username_4**: Note that also, $P = PSPACE$ implies that $NL \ne P$ since $NL \ne PSPACE$ ($NL \subseteq SPACE((\log n)^2) \subsetneq PSPACE$ by Savitch's theorem and the space hierarchy theorem).  

---

