<p>This question is inspired by this question <a href="https://cstheory.stackexchange.com/questions/19668/implications-between-mathsfl-mathsfp-and-mathsfnl-mathsfnp">Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?</a> </p>

<p>We do know that ${\bf L}$ could equal ${\bf NL}$ and at the same time ${\bf P}$ could be different from ${\bf NP}$. I was wondering whether or not the inequality between ${\bf L}$ and ${\bf NL}$ imply inequality between ${\bf P}$ and ${\bf NP}$. Or we just simply do not know... </p>

CC BY-SA 3.0
2013-11-08T00:04:05.390Z
It is not known like many other unknown implications in complexity theory. I don't think this and the previous question are good questions unless there is some good motivation or justification why one might expect them.
Kaveh
CC BY-SA 3.0
2013-11-08T12:07:50.517Z
I think the "Implications between **L** = **P** and **NL** = **NP**" question is more reasonable than this one: given the description of **NP** in terms of a polynomial time algorithm to check a witness, a naive intuition would suggest the conjecture (**L** = **P**) ⇒ (**NL** = **NP**). The reason for this question being less reasonable is that there is not a simple, formal reason for suspecting it to be the case, but understanding that *computational resources such as workspace and/or nondeterminism might not compose very simply* is a hard-won intuition.
Niel de Beaudrap
CC BY-SA 3.0
2013-11-08T12:15:46.683Z
For a good while, there were many basic (but precise) questions about quantum computing being asked on TCS.SE. While they weren't research level, I thought it worthwhile for them to be answered here, because *if not here then where?* Getting good answers for such technical subjects essentially involves taking a graduate course and/or knowing an expert personally; there's a heavy bias in the 'accessible' information on the 'Net towards being hasty transcripts of interactive protocols, or written for experts. This is also true of complexity theory: addressing such questions I think is good.
Niel de Beaudrap
CC BY-SA 3.0
2013-11-08T16:22:12.980Z
there is a simple reason not to expect such a symmetry: in many ways space and time have much different behavior in complexity theory & there are many examples of this. this is seen eg in simply comparing the space/time hierarchy theorems. but on the other hand there are deep connections... another concept to remember here. imagine that both separations are proven with totally different proofs/techniques. but then in a disconnected sense one does imply the other (because they are both true!)
vzn
CC BY-SA 3.0
2013-11-08T16:32:05.373Z
@Niel, you have a good point, but my worry is that there are two many possible implications. They are similar to asking "what is the relation between complexity classes X and Y?" for arbitrary two complexity classes. So I think these are not good questions if they are asked _without a good motivation_.
Kaveh
CC BY-SA 3.0
2013-11-08T18:12:29.383Z
@Kaveh: the solution on other StackExchange sites is usually to answer a few examples, and then once there are enough questions to demand a better response than ad hoc, to write a "canonical" question which captures the theme of the examples (and hopefully provides both intuition and resources for anyone asking similar questions).
Niel de Beaudrap
CC BY-SA 3.0
2013-11-08T18:48:12.087Z
@Niel, OK, that sounds reasonable.
Kaveh
<complexity-classes>
Does ${\bf L} \neq {\bf NL}$ imply ${\bf P} \neq {\bf NP}$?
user18304
# Does ${\bf L} \neq {\bf NL}$ imply ${\bf P} \neq {\bf NP}$?

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

This question is inspired by this question [Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?](https://cstheory.stackexchange.com/questions/19668/implications-between-mathsfl-mathsfp-and-mathsfnl-mathsfnp)

We do know that ${\bf L}$ could equal ${\bf NL}$ and at the same time ${\bf P}$ could be different from ${\bf NP}$. I was wondering whether or not the inequality between ${\bf L}$ and ${\bf NL}$ imply inequality between ${\bf P}$ and ${\bf NP}$. Or we just simply do not know...

**Tags:** complexity-classes
> **Comments:**
> **username_1**: It is not known like many other unknown implications in complexity theory. I don't think this and the previous question are good questions unless there is some good motivation or justification why one might expect them.  
> **username_2**: I think the "Implications between **L** = **P** and **NL** = **NP**" question is more reasonable than this one: given the description of **NP** in terms of a polynomial time algorithm to check a witness, a naive intuition would suggest the conjecture (**L** = **P**) ⇒ (**NL** = **NP**). The reason for this question being less reasonable is that there is not a simple, formal reason for suspecting it to be the case, but understanding that *computational resources such as workspace and/or nondeterminism might not compose very simply* is a hard-won intuition.  
> **username_2**: For a good while, there were many basic (but precise) questions about quantum computing being asked on TCS.SE. While they weren't research level, I thought it worthwhile for them to be answered here, because *if not here then where?* Getting good answers for such technical subjects essentially involves taking a graduate course and/or knowing an expert personally; there's a heavy bias in the 'accessible' information on the 'Net towards being hasty transcripts of interactive protocols, or written for experts. This is also true of complexity theory: addressing such questions I think is good.  
> **username_3**: there is a simple reason not to expect such a symmetry: in many ways space and time have much different behavior in complexity theory & there are many examples of this. this is seen eg in simply comparing the space/time hierarchy theorems. but on the other hand there are deep connections... another concept to remember here. imagine that both separations are proven with totally different proofs/techniques. but then in a disconnected sense one does imply the other (because they are both true!)  
> **username_1**: @Niel, you have a good point, but my worry is that there are two many possible implications. They are similar to asking "what is the relation between complexity classes X and Y?" for arbitrary two complexity classes. So I think these are not good questions if they are asked _without a good motivation_.  
> **username_2**: @Kaveh: the solution on other StackExchange sites is usually to answer a few examples, and then once there are enough questions to demand a better response than ad hoc, to write a "canonical" question which captures the theme of the examples (and hopefully provides both intuition and resources for anyone asking similar questions).  
> **username_1**: @Niel, OK, that sounds reasonable.  

---

## 0 answers

