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

CC BY-SA 3.0
2013-11-08T11:58:56.327Z
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
CC BY-SA 3.0
2013-11-05T13:55:35.513Z
2013-11-05T13:55:35.513Z
Mohammad Al-Turkistany
<p>If we can prove that  $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ? </p>

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

CC BY-SA 3.0
2013-11-05T14:38:32.587Z
Proving the converse would be pretty hard...
domotorp
CC BY-SA 3.0
2013-11-05T15:46:23.737Z
The converse boils to whether NL=P  implies L=P. This is not necessarily true unless L=NL.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-01-17T21:55:54.493Z
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!  https://cstheory.stackexchange.com/questions/31073/any-known-connections-between-open-problems-for-time-and-space-p-vs-l-np-vs-nl
Michael Wehar
<cc.complexity-theory><complexity-classes><nondeterminism>
Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?
Thatchaphol
# Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

(Asked by: username_0 on 2013-11-05)

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

**Tags:** cc.complexity-theory, complexity-classes, nondeterminism
> **Comments:**
> **username_1**: Proving the converse would be pretty hard...  
> **username_2**: The converse boils to whether NL=P  implies L=P. This is not necessarily true unless L=NL.  
> **username_3**: 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!  https://cstheory.stackexchange.com/questions/31073/any-known-connections-between-open-problems-for-time-and-space-p-vs-l-np-vs-nl  

---

## 1 answers

### Answer by username_2 on 2013-11-05. Score: 14 | Accepted answer

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

> **Comments:**
> **username_4**: 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.  

---

