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

  • $\begingroup$ 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. $\endgroup$ May 23, 2017 at 16:04
  • $\begingroup$ @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. $\endgroup$
    – Columbo
    May 23, 2017 at 16:15
  • $\begingroup$ 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.) $\endgroup$ May 23, 2017 at 17:04
  • $\begingroup$ @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. $\endgroup$
    – Columbo
    May 23, 2017 at 17:44
  • $\begingroup$ 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). $\endgroup$ May 23, 2017 at 18:52

1 Answer 1


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

If $\textbf{P} = \textbf{NP}$, the polynomial hierarchy collapses, i.e., $\textbf{P} = \textbf{PH}$. See also Can one amplify P=NP beyond P=PH? 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)? for information about why it seems hard to derive the implication $\textbf{P} = \textbf{PSPACE}$.

  • 4
    $\begingroup$ 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). $\endgroup$ May 22, 2017 at 22:34

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