LSPACE
Einfache Sprache
Hat eine TM logarithmische Platzkomplexität, dann kann es zwar die ganze Eingabe lesen, aber nicht zu speichern. Da aber Pointer in die Eingabe, dargestellt als binäre Zahl, bei Input-länge $n$ nur $\log n$ Speicherplatz brauchen, kann man mit Pointern hantieren.
Für die Logarithmische Platzkomlexität benutzen wir eine modifizierte TM, eine sogenannte Nur-Lesen-Eingabeband Turingmaschine, mit einer Eingabeband, was nur gelesen werden kann und einem Arbeitsband was man wie gewohnt lesen und schreiben kann.
Def. LSPACE
Die deterministische logarithmische Platzkomplexitätsklasse $\mathbf L$ ist die Klasse der Sprachen, die durch eine DTM im logarithmischem Raum entscheidbar sind. Also
$$\mathbf L = \mathbf{SPACE}(\log n)$$
Eine Sprache in $\mathbf L$ ist die Sprache Sprache 0^k1^k wie folgender Satz zeigt: Satz 0^k1^k ist L.
Sätze
- Satz Falls B in L und A log-raum reduzierbar auf B dann A in L
- Satz BRANCHING-PROG in L