EXPSPACE

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

In der Komplexitätstheorie steht EXPSPACE (Exponential Space) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch \mathcal O\left(2^{p(n)}\right) Platz entschieden werden können, wobei p(n) ein beliebiges Polynom ist. Betrachtet man nicht-determinisitsche Turingmaschinen erhält man die Klasse NEXPSPACE. Nach dem Satz von Savitch gilt EXPSPACE=NEXPSPACE.

In der DSPACE / NSPACE-Notation ausgedrückt gilt also:

\mbox{EXPSPACE} = \bigcup_{k \in \mathbb{N}} \mbox{DSPACE}\left(2^{n^k}\right) = \bigcup_{k \in \mathbb{N}} \mbox{NSPACE}\left(2^{n^k}\right).

Beziehung zu anderen Komplexitätsklassen[Bearbeiten]

Die folgenden Beziehungen sind bekannt:

NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE = NEXPSPACE

und weiters PSPACE \subset EXPSPACE

Weblinks[Bearbeiten]

  • EXPSPACE. In: Complexity Zoo. (englisch)

Literatur[Bearbeiten]

  • Christos H. Papadimitriou: Computational Complexity (Kapitel 20). Addison-Wesley, Reading/Mass. 1995, ISBN 0-201-53082-1.