EXPTIME

Pour les articles homonymes, voir EXP.

En théorie de la complexité, EXPTIME (ou EXP) est la classe de complexité qui est l'ensemble des problèmes de décision décidés par une machine de Turing déterministe en temps exponentiel.

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]}.

Via les machines de Turing alternantes, et via l'égalité entre la classe APSPACE (en espace polynomial sur une machine alternante) et EXPTIME, Chandra et Stockmeyer ont exhibé des jeux booléens à information parfaite à deux joueurs et des jeux sur des graphes qui sont EXPTIME-complets^[6].

Un des jeux booléens, EXPTIME-complet, est présenté comme un jeu à deux joueurs appelé PEEK. Une boîte est perforée et contient des plaques perforées du joueur 1 et des plaques perforées du joueur 2. Les joueurs jouent tour à tour : soit il ne fait rien soit il tire ou pousse une de ses plaques. Un des joueurs gagnent s'il arrive à aligner verticalement une série de trous à travers toute la boîte. Une instance de PEEK est la description des deux ensembles de plaques perforées (arbitrairement grandes). Plus formellement, le jeu PEEK, appelé G4 dans l'article de Chandra et Stockmeyer, est le suivant. En entrée, on se donne une formule booléenne sous forme normale disjonctive avec au plus 13 littéraux par clause. On se donne aussi une valuation initiale sur les 2k variables apparaissant dans la formule. L'ensemble des variables est partitionné en deux : les k variables contrôlés par le premier joueur et les k variables contrôlés par le deuxième. Le premier joueur qui rend la formule vrai gagne. Le problème de décision consiste à décider si le premier joueur a une stratégie gagnante.

Les travaux de Chandra Stockmeyer ont alors permis de montrer que des versions généralisées de jeux, comme les échecs^[7], les dames^[8] et le go^[9] sont EXPTIME-complets ; ces jeux ont été généralisés dans le sens où la taille du plateau est donnée en entrée du problème. Aussi, la logique contrainte est un outil pour démontrer la EXPTIME-dureté de certains jeux^[10].

Aussi, les travaux de Chandra et Stockmeyer ont permis à Littman de démontrer que le problème de la planification automatique où les actions sont non-déterministes et où l'agent a information parfaite est EXPTIME-dur^[11].

• Théorie de la complexité (informatique théorique)
• Classe de complexité
• E (complexité) : la classe des problèmes de EXPTIME qui ont un exposant linéaire en fonction de la taille, autrement dit E = DTIME${\displaystyle (2^{O(n)})}$.

• (en) La classe EXPTIME sur le Complexity Zoo

• Portail de l'informatique théorique