W obliczeniowej teorii złożoności L (znane również jako LSPACE lub DLOGSPACE) jest klasą złożoności zawierającą problemy decyzyjne, które można rozwiązać za pomocą deterministycznej maszyny Turinga przy użyciu logarytmicznej ilości zapisywalnej przestrzeni pamięci. Formalnie maszyna Turinga ma dwie taśmy, z których jedna koduje dane wejściowe i może być tylko odczytywana, podczas gdy druga taśma ma rozmiar logarytmiczny, ale można ją czytać i zapisywać. Przestrzeń logarytmiczna jest wystarczająca do przechowywania stałej liczby wskaźników na wejściu i logarytmicznej liczby flag boolowskich, a wiele podstawowych algorytmów pamięci logarytmicznej wykorzystuje w ten sposób pamięć.
Problemy L-zupełne i logiczna charakterystyka Każdy nietrywialny problem w L jest zupełny w przypadku redukcji przestrzeni logarytmicznej więc słabsze redukcje są wymagane do zidentyfikowania znaczących pojęć L- zupełności, przy czym najczęściej są to redukcje pierwszego rzędu.
Wynik Omera Reingolda z 2004 r. pokazuje, że USTCON, problem tego, czy istnieje ścieżka między dwoma wierzchołkami na danym nieskierowanym grafie jest w L, pokazując, że L = SL, ponieważ USTCON jest SL- kompletny.