NLSPACE

Einfache Sprache

Def. NLSPACE

Die nichtdeterministische logarithmische Platzkomplexitätsklasse $\mathbf{NL}$ ist die Klasse der Sprachen, die durch eine NDTM im logarithmischem Raum entscheidbar sind. Also

$$\mathbf{NL} = \mathbf{NSPACE}(\log n)$$

Sätze

• Satz NL ist gleich coNL