L (klasa złożoności)
 | Ten artykuł od 2022-09 wymaga zweryfikowania podanych informacji. |
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.
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. Włączenie L do P można również udowodnić bardziej bezpośrednio: decydent używający O (log n) miejsce nie może użyć więcej niż 2 O (log n) = n O (1) czas, ponieważ jest to całkowita liczba możliwych konfiguracji.
L odnosi się ponadto do klasy NC w następujący sposób: NC 1⊆ L. ⊆ NL ⊆ NC 2. Biorąc równoległy komputer C z wielomianową ilością O (n-k), procesorów dla pewnej stałej k, każdy problem, który może być rozwiązany na C w o (log n) czasu jest w L, a każdy problem w L można rozwiązać w O (log 2 n) czas na C.
Ważne otwarte problemy obejmują to, czy L = P, i czy L = NL.