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:

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

Weblinks

NSPACE. In: Complexity Zoo. (englisch)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.