# Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

If we can prove that $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ?

I thought it is the case, but I cannot prove it (also for the converse).

• Proving the converse would be pretty hard... – domotorp Nov 5 '13 at 14:38
• The converse boils to whether NL=P implies L=P. This is not necessarily true unless L=NL. – Mohammad Al-Turkistany Nov 5 '13 at 15:46
• I posted a related question about the relationships between P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L. If you're interested, please feel free to take a look. Thank you! cstheory.stackexchange.com/questions/31073/… – Michael Wehar Jan 17 at 21:55

No. It is possible that L=P and that P != NP which implies that NL != NP since NL is contained in P.

• I think it would probably be helpful, rather than merely asserting this outright, to give some intuition how this could be. Considering the construction NP = ∃P (i.e. its definition in terms of checking a witness using a polytime algorithm),I can see how one might guess that if P = L, that we could simply obtain NP = ∃L = NL by substitution. Perhaps some remarks on how the logarithmic limitation on the work tape would help to indicate why this is not the case. – Niel de Beaudrap Nov 8 '13 at 11:58