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 der DSPACE / NSPACE-Notation ausgedrückt gilt 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 sind 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 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.[1] 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

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