5
$\begingroup$

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.

$\endgroup$
10

3 Answers 3

5
$\begingroup$

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:

$\endgroup$
1
$\begingroup$

We know a little bit more. We know that NL is different from PSPACE. Savitch's theorem implies that NL is included in SPACE(log^2(n)). The space hiearchy theorem implies that this latter class is strictly included in PSPACE.

$\endgroup$
-1
$\begingroup$

There is a purported proof of L different from NP. This is recent work, and it looks serious http://arxiv.org/abs/2404.16562

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.