NSPACE

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

NSPACE 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:

\mbox{NPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k) = \mbox{coNPSPACE}

Weblinks[Bearbeiten]

  • NSPACE. In: Complexity Zoo. (englisch)