EXPTIME

Si l'on appelle ${\displaystyle {\mbox{DTIME}}(t(n))}$, l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing déterministes utilisant un temps ${\displaystyle O(t(n))}$ pour une fonction ${\displaystyle t}$ en la taille de l'entrée ${\displaystyle n}$, alors on peut définir EXPTIME formellement par :

${\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right).}$

Comme l'illustre l'image de droite, on a les inclusions suivantes : P ${\displaystyle \scriptstyle \subseteq }$ NP ${\displaystyle \scriptstyle \subseteq }$ PSPACE ${\displaystyle \scriptstyle \subseteq }$ EXPTIME.

EXPTIME est une classe relativement grosse, qui contient des problèmes considérés comme impossibles à résoudre de façon efficace. Mais il existe des classes plus grosses comme EXPSPACE et NEXPTIME (respectivement les problèmes pouvant être résolus en espace exponentiel, et en temps exponentiel sur machine non déterministe).

Par un argument de « padding » (remplissage), on a le théorème suivant^[1], lié au problème P=NP :

De plus d'après le théorème de hiérarchie en temps déterministe, la classe P est différente de la classe EXPTIME.

La classe EXPTIME est égale à la classe APSPACE, l'équivalent de PSPACE sur machine de Turing alternante, d'après le théorème de Chandra-Kozen-Stockmeyer^[2].

En complexité descriptive, EXPTIME correspond à SO(LFP), c'est-à-dire à la logique du second ordre avec plus petit point fixe^[3].

Le problème de l'arrêt d'une machine de Turing après k pas de temps (où k est écrit en notation binaire) est EXPTIME-complet^[4]. C'est une restriction du problème de l'arrêt, qui est indécidable dans le cas général.

Le problème de satisfiabilité des logiques suivantes sont EXPTIME-complets :

• la logique temporelle CTL est EXPTIME-complet^{[réf. nécessaire]} ;
• la logique propositionnelle dynamique (PDL)^[5].

Des versions succinctes de certains problèmes P-complets sont EXPTIME-complets, comme SUCCINCT CIRCUIT VALUE^{[réf. nécessaire]}.