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.
Anche se non noto, quali sono gli attributi più comunemente attribuiti di L in relazione alle classi di complessità P?
strettamente contenuto in P o uguale a P contenuto in P o uguale a P strettamente contenuto in P o uguale a P