Jedną z konsekwencji tego jest prosta logiczna charakterystyka L: zawiera dokładnie te języki, które można wyrazić w logice pierwszego rzędu, z dodanym przemiennym operatorem domknięcie przechodniego (teoretycznie w grafie zmienia to każdą spójną składową w klikę). Ten wynik ma zastosowanie do języków zapytań bazy danych: złożoność danych zapytania jest zdefiniowana jako złożoność odpowiedzi na ustalone zapytanie, biorąc pod uwagę rozmiar danych jako zmienną wejściową. W tym celu zapytania dotyczące relacyjnych baz danych z pełną informacją (bez pojęcia zer) wyrażone na przykład w relacyjnej algebrze znajdują się w L.
Powiązane klasy złożoności L jest podklasą NL, która jest klasą języków rozstrzygalnych w przestrzeni logarytmicznej na niedeterministycznej maszynie Turinga. Problem w NL można przekształcić w problem osiągalności na grafie skierowanym reprezentującym stany i przejścia stanów maszyny niedeterministycznej, a związana przestrzeń logarytmiczna implikuje, że wykres ten ma wielomianową liczbę wierzchołków i krawędzi, z których wynika, że NL jest zawarty w klasie złożoności P problemów możliwych do rozwiązania w deterministycznym czasie wielomianowym. Tak więc L ⊆ NL ⊆ P.