# Is it possible that $L=NP$?

According to Wikipedia and other sources, the question whether $$L=P$$ is an open problem, and of course everyone is familiar with the problem of whether $$P=NP$$. However, I found absolutely no information online regarding a possible equality between $$L$$ and $$NP$$.

Such an equality doesn't directly violate the space-hierarchy theorem or the time-hierarchy theorem, and so I don't have any idea how to disprove it.

• Have you checked the complexity zoo?
– Raphael
Jan 19 '19 at 10:26
• It's an open question: rjlipton.wordpress.com/2011/11/11/taking-passes-at-np-versus-l Jan 19 '19 at 10:30
• See also 47522 (If P=NP, then is L=NL?) Jan 19 '19 at 10:32
• The only thing we know is $\text{L} \subsetneq \text{PSPACE}$. Jan 19 '19 at 10:33
• @PålGD Not only "for which question is that not the case?", but also the scope/level of the other questions linked is much broader/higher, and I sincerely think that this post has a right to exist merely because it is a relatively basic and focused question whose answer is hard to find otherwise. Jan 19 '19 at 10:51

The question whether $$L = NP$$ is an open problem [1], so yes, it is possible. However, it is considered unlikely, or in other words, most believe that $$L \subsetneq P \subsetneq NP \subsetneq PSPACE$$, but we only know that $$L \subsetneq PSPACE$$ [2, 3].