I asked this question on cstheory.se before, where someone pointed out that it is equivalent to asking whether P=NP implies NL=P (thus I edited the question accordingly).

However, my supervisor claims that actually, connectivity being NP-complete implies that NL=P=NP. I can't see why this would be the case; the only additional information we're assuming is that there is a polynomial-time reduction from any NP problem to an NL problem, which does not imply that there exists a corresponding log-space reduction. Wikipedia also mentions

Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions.

... which seems to support my argument.


If NP completeness of connectivity implies $\mathsf{NL}=\mathsf{P}=\mathsf{NP}$, then $\mathsf{P}\neq\mathsf{PSPACE}$. To see why, suppose $\mathsf{P}=\mathsf{PSPACE}$, then connectivity (and any other non trivial language in P) is NP complete, thus $\mathsf{NL}=\mathsf{P}=\mathsf{PSPACE}$ (by our original assumption), which contradicts the space hierarchy theorem.

This means such implication is not yet known. For completeness, I'll add that a negative answer would imply the existence of an NP complete problem which is not complete under logspace reductions (if all NP complete problems were also complete under logspace reductions, then NP completeness of connectivity implies $\mathsf{NL}=\mathsf{NP})$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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