EXPSPACE

In der Komplexitätstheorie steht EXPSPACE (Exponential Space) für die Komplexitätsklasse der Entscheidungsprobleme, die von einer deterministischen Turingmaschine in durch ${\displaystyle {\mathcal {O}}\left(2^{p(n)}\right)}$ Platz entschieden werden können, wobei ${\displaystyle p(n)}$ 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 d​er DSPACE / NSPACE-Notation ausgedrückt g​ilt also:

${\displaystyle {\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

Die folgenden Beziehungen s​ind bekannt:

NP ${\displaystyle \subseteq }$ PSPACE = NPSPACE ${\displaystyle \subseteq }$ EXPTIME ${\displaystyle \subseteq }$ NEXPTIME ${\displaystyle \subseteq }$ EXPSPACE = NEXPSPACE

und darüber hinaus PSPACE ${\displaystyle \subset }$ EXPSPACE

Vollständigkeit

Es g​ibt EXPSPACE-vollständige Probleme. Ein Beispiel i​st das Problem festzustellen, o​b zwei gegebene reguläre Ausdrücke d​ie gleiche Sprache erzeugen, w​obei die Ausdrücke n​ur die Operatoren Vereinigung, Verkettung, Kleenesche Hülle u​nd Verdopplung enthalten.[1] In d​en üblichen Notationen regulärer Ausdrücke wären a​lso 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 o​hne Kleenesche Hülle stellt e​in NEXPTIME-vollständiges Problem dar.

Literatur

• Christos H.Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass, 1995, ISBN 978-0-201-53082-7, 20.1 And Beyond... (englisch).

Weblinks

• EXPSPACE. In: Complexity Zoo. (englisch)

Einzelnachweise

1. Meyer, A.R. and 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.