HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is it possible that $L=NP$?

Submitted by: @import:stackexchange-cs··
0
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.

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:

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