# Is it possible that $\mathsf{L} = \mathsf{NP}$?

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 ;-))

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

## 1 Answer

$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.

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