Allo stesso modo, non è noto se L (l' insieme di tutti i problemi che possono essere risolti nello spazio logaritmico) è strettamente contenuto in P o uguale a P. Anche in questo caso, ci sono molte classi di complessità tra i due, come NL e NC, e non è noto se sono classi distinte o uguali.
Quali sono le due classi di complessità tra L e P?
NL e NC NL e NC NL e NC