4

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

Columbo
  • 143
  • 6
  • 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 May 23 '17 at 16:04
  • @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 May 23 '17 at 16:15
  • 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 May 23 '17 at 17:04
  • @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 May 23 '17 at 17:44
  • 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 May 23 '17 at 18:52
  • @HuckBennett Elaborate, please. Are you saying that reachability being NP-complete does imply NP!=PSPACE? – Columbo May 27 '17 at 08:20
  • 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 May 27 '17 at 22:02
  • @HuckBennett I don't think so. Or perhaps we're talking past each other. – Columbo May 27 '17 at 22:04
  • 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 May 27 '17 at 23:02
  • 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 May 28 '17 at 17:39

1 Answers1

13

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

D.W.
  • 12,054
  • 2
  • 34
  • 80
  • 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). – Mikhail Rudoy May 22 '17 at 22:34