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

  • 3
    $\begingroup$ Proving the converse would be pretty hard... $\endgroup$
    – domotorp
    Nov 5 '13 at 14:38
  • $\begingroup$ The converse boils to whether NL=P implies L=P. This is not necessarily true unless L=NL. $\endgroup$ Nov 5 '13 at 15:46
  • 1
    $\begingroup$ 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/… $\endgroup$ Jan 17 '19 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.

  • 5
    $\begingroup$ 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. $\endgroup$ Nov 8 '13 at 11:58

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.