NSPACE

NSPACE

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

  • NSPACE. In: Complexity Zoo. (englisch)

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   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

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”