5
$\begingroup$

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

$\endgroup$

closed as off-topic by D.W., Kaveh, user6973, Jan Johannsen, Emil Jeřábek May 23 '17 at 8:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – D.W., Kaveh, Community, Jan Johannsen, Emil Jeřábek
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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$ – Huck Bennett May 23 '17 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 '17 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$ – Huck Bennett May 23 '17 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 '17 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$ – Huck Bennett May 23 '17 at 18:52
13
$\begingroup$

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

$\endgroup$
  • 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$ – Mikhail Rudoy May 22 '17 at 22:34

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