: "EXP" adressiert hier um; für anderen Gebrauch, sieh exp.

In der rechenbetonten Kompliziertheitstheorie die Kompliziertheitsklasse ist EXPTIME (hat manchmal EXP genannt), der Satz aller Entscheidungsprobleme, die durch eine deterministische Maschine von Turing in O (2) Zeit lösbar sind, wo p (n) eine polynomische Funktion von n ist.

In Bezug auf DTIME,

Wir wissen

:P NP PSPACE EXPTIME NEXPTIME EXPSPACE

und auch, als Hierarchie-Lehrsatz und der Raumhierarchie-Lehrsatz, das

:P EXPTIME und NP NEXPTIME und PSPACE EXPSPACE

so müssen mindestens eine der ersten drei Einschließungen und mindestens eine der letzten drei Einschließungen richtig sein, aber es ist nicht bekannt, die sind. Die meisten Experten glauben, dass alle Einschließungen richtig sind. Es ist auch dass wenn, dann, die Klasse von Problemen bekannt, die in der Exponentialzeit durch eine nichtdeterministische Maschine von Turing lösbar sind. Genauer, EXPTIME  NEXPTIME wenn, und nur wenn dort spärliche Sprachen in NP bestehen, die nicht in P sind.

EXPTIME kann auch als die Raumklasse APSPACE, die Probleme wiederformuliert werden, die durch eine Wechselmaschine von Turing im polynomischen Raum gelöst werden können. Das ist eine Weise zu sehen, dass PSPACE EXPTIME, da eine Wechselmaschine von Turing mindestens so stark ist wie eine deterministische Maschine von Turing.

EXPTIME ist eine Klasse in einer Exponentialhierarchie von Kompliziertheitsklassen mit zunehmend höheren Zeitgrenzen. Die 2-EXPTIME Klasse wird ähnlich zu EXPTIME, aber mit doppelt Exponential-fristgebunden definiert. Das kann zu höher und höhere Zeitgrenzen verallgemeinert werden.

EXPTIME-abgeschlossen

Ein Entscheidungsproblem ist EXPTIME-abgeschlossen, wenn es in EXPTIME ist, und jedes Problem in EXPTIME 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 Problemen, die EXPTIME-abgeschlossen sind, könnte als die härtesten Probleme in EXPTIME gedacht werden. Bemerken Sie, dass, obwohl wir nicht wissen, ob NP eine Teilmenge von P ist oder nicht, wir wissen, dass EXPTIME-ganze Probleme nicht in P sind; es ist bewiesen worden, dass diese Probleme in der polynomischen Zeit als Hierarchie-Lehrsatz nicht behoben werden können.

In der Berechenbarkeitstheorie ist eines der grundlegenden unentscheidbaren Probleme das des Entscheidens, ob eine deterministische Maschine von Turing (DTM) hinkt. Eines der grundsätzlichsten EXPTIME-ganzen Probleme ist eine einfachere Version davon, das fragt, ob ein DTM in an den meisten K-Schritten hinkt. Es ist in EXPTIME, weil eine triviale Simulation O (k) Zeit verlangt, und der Eingang k mit O verschlüsselt wird (loggen Sie k) Bit. Es ist EXPTIME-abgeschlossen, weil, grob das Sprechen, wir es verwenden können, um zu bestimmen, ob eine Maschine, die ein EXPTIME Problem behebt, in einer Exponentialzahl von Schritten akzeptiert; es wird mehr nicht verwenden. Dasselbe Problem mit der Zahl von im unären geschriebenen Schritten ist P-complete.

Andere Beispiele von EXPTIME-ganzen Problemen schließen das Problem ein, eine Position im verallgemeinerten Schach, den Kontrolleuren zu bewerten, oder Gehen (mit japanischen Ko-Regeln). Diese Spiele haben eine Chance, EXPTIME-abgeschlossen zu sein, weil Spiele für mehrere Bewegungen dauern können, der in der Größe des Ausschusses Exponential-ist. Im Gehen Beispiel ist die japanische Ko-Regel genug unnachgiebig, um EXPTIME-Vollständigkeit einzubeziehen, aber es ist nicht bekannt, ob die lenksameren amerikanischen oder chinesischen Regeln für das Spiel EXPTIME-abgeschlossen sind.

Im Vergleich sind verallgemeinerte Spiele, die für mehrere Bewegungen dauern können, der Polynom in der Größe des Ausschusses ist, häufig PSPACE-abgeschlossen. Dasselbe trifft auf exponential lange Spiele zu, in denen Nichtwiederholung automatisch ist.

Ein anderer Satz von wichtigen EXPTIME-ganzen Problemen bezieht sich auf kurz gefasste Stromkreise. Kurz gefasste Stromkreise sind einfache Maschinen, die verwendet sind, um einige Graphen in exponential weniger Raum zu beschreiben. Sie akzeptieren zwei Scheitelpunkt-Zahlen, wie eingegeben, und Produktion, ob es einen Rand zwischen ihnen gibt. Für viele natürliche P-complete Graph-Probleme, wo der Graph in einer natürlichen Darstellung wie eine Angrenzen-Matrix ausgedrückt wird, dasselbe Problem auf einer kurz gefassten Stromkreis-Darstellung behebend, ist EXPTIME-abgeschlossen, weil der Eingang exponential kleiner ist; aber das verlangt nichttrivialen Beweis, da kurz gefasste Stromkreise nur eine Unterklasse von Graphen beschreiben können.