14
$\begingroup$

This question is inspired by this question Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

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

$\endgroup$
7
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Nov 8 '13 at 0:04
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 8 '13 at 12:07
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 8 '13 at 12:15
  • $\begingroup$ 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!) $\endgroup$
    – vzn
    Nov 8 '13 at 16:22
  • 3
    $\begingroup$ @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). $\endgroup$ Nov 8 '13 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.