patternMinor
Is it possible that $L=NP$?
Viewed 0 times
possiblethatstackoverflow
Problem
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.
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.
Solution
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].
References:
References:
- [1] Taking Passes at NP Versus L — Gödel's Lost Letter and P=NP
- [2] L/P/PSpace vs P/NP — cstheory.stackexchange.com
- [3] If P=NP, then is L=NL? — cs.stackexchange.com
Context
StackExchange Computer Science Q#103073, answer score: 4
Revisions (0)
No revisions yet.