10
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ Proving the converse would be pretty hard... $\endgroup$
    – domotorp
    Nov 5, 2013 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, 2013 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, 2019 at 21:55

1 Answer 1

14
$\begingroup$

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

$\endgroup$
1
  • 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, 2013 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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