NSPACE

NSPACE (selten auch NTAPE, von englisch: Non-deterministic Turing machine tape) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der theoretischen Informatik.

Dort steht NSPACE(f) für die Platzkomplexitätsklasse der Entscheidungsprobleme, die von einer Nichtdeterministischen Turingmaschine mit Platzbedarf O(f) gelöst werden können. Es ist das nichtdeterministische Gegenstück zu DSPACE. NSPACE(f(n)) ist gegen Komplement abgeschlossen (Satz von Immerman und Szelepcsényi).

Mit NSPACE werden häufig andere Komplexitätsklassen definiert. So kann NPSPACE wie folgt aus NSPACE hergeleitet werden:

${\displaystyle {\mbox{NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})}$

Weblinks

• NSPACE. In: Complexity Zoo. (englisch)