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).
10
$\begingroup$
$\endgroup$
-
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$ – Mohammad Al-Turkistany 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$ – Michael Wehar Jan 17 at 21:55
14
$\begingroup$
$\endgroup$
No. It is possible that L=P and that P != NP which implies that NL != NP since NL is contained in P.
answered Nov 5 '13 at 13:55
-
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$ – Niel de Beaudrap Nov 8 '13 at 11:58
