imported>YMS: Sprache, Format

2024-04-17T19:51:54Z

Sprache, Format

Neue Seite

In der [[Komplexitätstheorie]] steht '''EXPSPACE''' (Exponential Space) für die [[Komplexitätsklasse]] der [[Entscheidbar|Entscheidungsprobleme]], die von einer [[Determinismus (Algorithmus)|deterministischen]] [[Turingmaschine]] in durch <math>\mathcal O\left(2^{p(n)}\right)</math> [[Platzkomplexität|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 (Komplexitätsklasse)|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 [[Regulärer Ausdruck#Semantik|Operatoren]] Vereinigung, Verkettung, [[Kleenesche Hülle]] und Verdopplung enthalten.<ref>A. R. Meyer, [[Larry Stockmeyer|L. Stockmeyer]]: [http://people.csail.mit.edu/meyer/rsq.pdf 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: <code>(''x''|''y'')</code>, erkennt <code>''x''</code> oder <code>''y''</code>,
* Verkettung: <code>''xy''</code>, erkennt <code>''x''</code> und dann <code>''y''</code>,
* Kleenesche Hülle: <code>''x''*</code>, erkennt <code>''x''</code> beliebig oft, ggf. gar nicht, und
* Dopplung: <code>''x''{2}</code>, erkennt <code>''x''</code> genau zweimal,
erlaubt, wobei <code>''x''</code> und <code>''y''</code> bereits nach diesem Schema korrekt gebildete Ausdrücke oder Literale aus dem gegebenen Alphabet sind. Die Zeichen <code>(</code>, <code>|</code>, <code>)</code>, <code>*</code> und <code>{2}</code> werden als nicht Teil des Literal-Alphabets aufgefasst.
Die Dopplung ist nur ein Symbol mehr, wohingegen das Verketten von <code>''x''</code> 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 ==
* {{Literatur| Autor=[[Christos Papadimitriou|Christos H.Papadimitriou]]| Titel=Computational Complexity| Verlag=Addison-Wesley, Reading/Mass| Datum=1995| Sprache=en| Kapitel=20.1 And Beyond...| ISBN=978-0-201-53082-7}}

== Weblinks ==
* {{Complexity Zoo|EXPSPACE|E#expspace}}

== Einzelnachweise ==
<references />

[[Kategorie:Komplexitätsklasse]]

EXPSPACE - Versionsgeschichte

imported>YMS: Sprache, Format