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 Platz entschieden werden können, wobei 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:

Beziehung zu anderen Komplexitätsklassen[Bearbeiten | Quelltext bearbeiten]

Die folgenden Beziehungen sind bekannt:

NP PSPACE EXPTIME NEXPTIME EXPSPACE = NEXPSPACE

und weiters PSPACE EXPSPACE

Vollständigkeit[Bearbeiten | Quelltext bearbeiten]

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.

Weblinks[Bearbeiten | Quelltext bearbeiten]

  • EXPSPACE. In: Complexity Zoo. (englisch)

Literatur[Bearbeiten | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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.