EXPSPACE

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

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

<math>\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).</math>

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

NP <math>\subseteq</math> PSPACE = NPSPACE <math>\subseteq</math> EXPTIME <math>\subseteq</math> NEXPTIME <math>\subseteq</math> EXPSPACE = NEXPSPACE

und darüber hinaus PSPACE <math>\subset</math> EXPSPACE

Vollständigkeit

Es gibt EXPSPACE-vollständige Probleme. Ein Beispiel ist das Problem festzustellen, ob zwei gegebene reguläre Ausdrücke die gleiche Sprache erzeugen, wobei die Ausdrücke nur die Operatoren Vereinigung, Verkettung, Kleenesche Hülle und Verdopplung enthalten.<ref>A. R. Meyer, L. Stockmeyer: The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, S. 125–129.</ref> In den üblichen Notationen regulärer Ausdrücke wären also nur

Vereinigung: (x|y), erkennt x oder y,
Verkettung: xy, erkennt x und dann y,
Kleenesche Hülle: x*, erkennt x beliebig oft, ggf. gar nicht, und
Dopplung: x{2}, erkennt x genau zweimal,

erlaubt, wobei x und y bereits nach diesem Schema korrekt gebildete Ausdrücke oder Literale aus dem gegebenen Alphabet sind. Die Zeichen (, |, ), * und {2} werden als nicht Teil des Literal-Alphabets aufgefasst. Die Dopplung ist nur ein Symbol mehr, wohingegen das Verketten von x mit sich selbst die Größe der Eingabe maßgeblich erhöht.

Dieselbe Frage ohne Kleenesche Hülle stellt ein NEXPTIME-vollständiges Problem dar.

Literatur

{{#invoke:Vorlage:Literatur|f}}

Weblinks

EXPSPACE. In: Complexity Zoo. (englisch)

Einzelnachweise