# Does graph connectivity being NP-complete imply NL=P?

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