NSPACE

In computational complexity theory, the complexity class NSPACE(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine using space O(f(n)), and unlimited time. It is the non-deterministic counterpart of DSPACE.

Several important complexity classes can be defined in terms of NSPACE. These include:

• REG = DSPACE(O(1)) = NSPACE(O(1)), where REG is the class of regular languages (nondeterminism does not add power in constant space).
• NL = NSPACE(O(log n))
• CSL = NSPACE(O(n)), where CSL is the class of context-sensitive languages.
• PSPACE = NPSPACE = $\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)$
• EXPSPACE = NEXPSPACE = $\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})$

The last two results above follow from Savitch's theorem, which states that for any function f(n) ≥ log(n),

NSPACE(f(n)) ⊆ DSPACE(f²(n)).

The Immerman–Szelepcsényi theorem states that NSPACE(s(n)) is closed under complement for every function s(n) ≥ log n.

NSPACE can be related to DTIME as follows. For any space constructible function s(n),

$\mbox{NSPACE}(s(n)) \subseteq \bigcup_{k \geq 1} \mbox{DTIME}(2^{k \cdot s(n)})$

A futher generalization is ASPACE, defined with alternating Turing machines.

References

Complexity Zoo: NSPACE(f(n)).

P ≟ NP

This theoretical computer science-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Complexity classes Computational resources Theoretical computer science stubs Wikimedia Foundation. 2010. Игры ⚽ Нужно сделать НИР? Jacques Poos DSPACE Look at other dictionaries: 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)… …   Deutsch Wikipedia NSPACE — En teoría de la complejidad computacional, la clase de complejidad NSPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la… …   Wikipedia Español NSPACE — En teoría de la complejidad computacional, la clase de complejidad NSPACE(f(n)) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no determinista en espacio O(f(n)) y tiempo ilimitado. NSPACE es la… …   Enciclopedia Universal Turingmaschine mit Zusatzeingabe — Eine Turingmaschine mit Zusatzeingabe ist ein zu Nichtdeterministischen Turingmaschinen äquivalentes Berechnungsmodell der Theoretischen Informatik. Inhaltsverzeichnis 1 Informelle Beschreibung 2 Definition 2.1 Turingmaschine mit Zusatzeingabe …   Deutsch Wikipedia Immerman–Szelepcsényi theorem — The Immerman–Szelepcsényi Theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE = co NSPACE. In other words, if a… …   Wikipedia Jerarquía de clases de complejidad acotadas por espacio — En teoría de la complejidad computacional se utilizan diferentes clases de complejidad para catalogar familias de problemas de decisión en relación con la cantidad de espacio que utilizan para ser resueltos. Estas clases de complejidad pueden ser …   Wikipedia Español Liste von Komplexitätsklassen — Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch,… …   Deutsch Wikipedia Satz von Immerman und Szelepcseny — Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NSPACE unter dem Komplement abgeschlossen ist. Lange nahm man an, dass die Klasse NSPACE genauso wie die Klasse NTIME nicht unter dem… …   Deutsch Wikipedia Satz von Immerman und Szelepcsény — Der Satz von Immerman und Szelepcsényi ist ein Satz aus der Komplexitätstheorie und besagt, dass die Klasse NSPACE unter dem Komplement abgeschlossen ist. Lange nahm man an, dass die Klasse NSPACE genauso wie die Klasse NTIME nicht unter dem… …   Deutsch Wikipedia Automate linéairement borné — En informatique théorique, et en particulier en théorie des automates, un automate linéairement borné (en anglais linear bounded automaton, abrégé en LBA) est une machine de Turing non déterministe assujettie à des restrictions dans son mode… …   Wikipédia en Français 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”