In der Kompliziertheitstheorie ist EXPSPACE der Satz aller Entscheidungsprobleme, die durch eine deterministische Maschine von Turing in O (2) Raum lösbar sind, wo p (n) eine polynomische Funktion von n ist. (Einige Autoren schränken p (n) ein, um eine geradlinige Funktion zu sein, aber die meisten Autoren nennen stattdessen die resultierende Klasse ESPACE.), Wenn wir eine nichtdeterministische Maschine statt dessen verwenden, bekommen wir die Klasse NEXPSPACE, der EXPSPACE durch den Lehrsatz von Savitch gleich ist.

In Bezug auf DSPACE und NSPACE,

Ein Entscheidungsproblem ist EXPSPACE-abgeschlossen, wenn es in EXPSPACE ist, und jedes Problem in EXPSPACE die polynomisch-malige eine Verminderung dazu hat. Mit anderen Worten gibt es einen polynomisch-maligen Algorithmus, der Beispiele von einem zu Beispielen von anderem mit derselben Antwort umgestaltet. Von EXPSPACE-ganzen Problemen könnte als die härtesten Probleme in EXPSPACE gedacht werden.

EXPSPACE ist eine strenge Obermenge von PSPACE, NP und P und wird geglaubt, eine strenge Obermenge von EXPTIME zu sein.

Ein Beispiel eines EXPSPACE-ganzen Problems ist das Problem des Erkennens, ob zwei regelmäßige Ausdrücke verschiedene Sprachen vertreten, wo die Ausdrücke auf vier Maschinenbediener beschränkt werden: Vereinigung, Verkettung, der Stern von Kleene (Null oder mehr Kopien eines Ausdrucks), und Quadrieren (zwei Kopien eines Ausdrucks).

Wenn der Stern von Kleene ausgelassen wird, dann wird dieses Problem NEXPTIME-abgeschlossen, der EXPTIME-abgeschlossen ähnlich ist, außer ihm wird in Bezug auf nichtdeterministische Maschinen von Turing definiert aber nicht deterministisch.

Es ist auch von L. Berman 1980 gezeigt worden, dass das Problem, jede Behauptung der ersten Ordnung über reelle Zahlen nachzuprüfen zu/fälschen, die nur Hinzufügung und Vergleich einschließt (aber keine Multiplikation) ist in EXPSPACE.

Siehe auch

• Spielkompliziertheit
• L. Berman Die Kompliziertheit von logischen Theorien, Theoretische Informatik 11:71-78, 1980.

• Abschnitt 9.1.1: Exponentialraumvollständigkeit, Seiten 313-317. Demonstriert, dass die Bestimmung der Gleichwertigkeit von regelmäßigen Ausdrücken mit exponentiation EXPSPACE-abgeschlossen ist.