L

Mit L oder LOGSPACE bezeichnet man die Klasse $\operatorname{DSPACE}(\log)$. Für sublinearen Speicherverbrauch vereinbart man, dass die Eingabe in einem eigenen Read-Only-Band übergeben wird, da dieser einem ansonsten schon linear viel zusätzlichen Speicherplatz brächte.

Beispiele

k-Cliquen in Graphen

Das Finden von k-Cliquen in einem graphen liegt it $L$: Wir probieren alle $k$-tupel an Knoten des Graphen durch, und überprüfen, ob sie eine Clique bilden. Zum Speichern der Adresse eines Knotens speichern wir eine Zahl, diese braucht logarithmisch viel Platz, entsprechend brauchen $k$ zahlen ebenfalls logarithmisch viel Platz.

Erreichbarkeit in Graphen

Der Beweis ist äußerst schwierig und erst seit den Neunzigern bekannt. Trotzdem ein netter Zusammenhang,