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$?
10
-
$\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 BennettCommented 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$– ColumboCommented 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$– Huck BennettCommented 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$– ColumboCommented 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$– Huck BennettCommented May 23, 2017 at 18:52
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
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$ Commented May 22, 2017 at 22:34