NSPACE

Einfache Sprache

Def. NSPACE

Sei $t:\mathbb N\to \mathbb R^+$ ein Funktion. Die nichtdeterministische Platzkomplexitätsklasse

$$\mathbf{NSPACE}(t(n))$$

ist definiert als die Menge aller Sprachen, die von einer Nichtdeterministische Turingmaschine mit Platzkomplexität Big O $O(t(n))$ entscheidbar sind.