SPACE

Einfache Sprache

Def. SPACE

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

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

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

Beispiel

SAT ist einfach in SPACE lösbar. Es werden einfach alle möglichen Belegungen ausprobiert. Dabei wird der Platz immer wiederverwendet.