EXPSPACE

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

EXPSPACE = ⋃ k ∈ N DSPACE ( 2 n k ) = ⋃ k ∈ N NSPACE ( 2 n k ) . {\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.