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}$

[Bearbeiten] Weblinks