2
$\begingroup$

When I studied computer science 10 years ago, it was still an open question whether $\mathsf{L}$ and $\mathsf{NP}$ are truly different classes. Is that still the case or has the inequality been proven in the meantime?

(I know this is a somewhat stupid question, but there's nothing about it in the complexity zoo, and googling L and NP is surprisingly ineffective ;-))

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ books.google.co.il/… You can check out the paragraph about separating $L, NP$ here (section 3 in the linked page). $\endgroup$ – Ariel May 6 '16 at 7:38
  • 1
    $\begingroup$ Possible, but unlikely. $\endgroup$ – Yuval Filmus May 6 '16 at 8:21
5
$\begingroup$

$L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$

From space hierarchy and time hierarchy theorems we can prove that

$L \subsetneq PSPACE$

$NL \subsetneq NPSPACE$

Note that we know $PSPACE = NPSPACE$.

$P \subsetneq EXP$

$NP \subsetneq NEXP$

Note that we don't know if $EXP \subsetneq NEXP$.

Whether the other inclusions are strict, are still open problems. Even though there are no proofs, many, but not all, believe most of the inclusions to be strict.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Note that ​ NPSPACE = PSPACE . ​ ​ ​ ​ $\endgroup$ – user12859 May 6 '16 at 8:39
  • $\begingroup$ True but I was using only space and time hierarchy theorems. And I did not mention NPSPACE in the inclusion list. $\endgroup$ – Shreesh May 6 '16 at 9:39
  • 1
    $\begingroup$ Anyway I have added a note that NPSPACE=PSPACE. $\endgroup$ – Shreesh May 6 '16 at 9:42

Your Answer

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

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