L (Komplexitätsklasse)

In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss hierbei vorausgesetzt werden, dass die Eingabe für das Entscheidungsproblem auf einem separaten Eingabeband gegeben ist. Dieses kann nur gelesen werden und wird für die Angabe des Platzverbrauchs nicht berücksichtigt.