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.
Définition formelle
[modifier | modifier le code]Si l'on appelle , l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing déterministes utilisant un temps pour une fonction en la taille de l'entrée , alors on peut définir EXPTIME formellement par :
Propriétés
[modifier | modifier le code]
Comme l'illustre l'image de droite, on a les inclusions suivantes : P NP PSPACE 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 :
Théorème — Si EXPTIMENEXPTIME alors PNP
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].
Problèmes EXPTIME-complets
[modifier | modifier le code]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].
EXPTIME et jeux à deux joueurs
[modifier | modifier le code]
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].
Notes et références
[modifier | modifier le code]- (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 2.6.2 (« EXP and NEXP »).
- Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, no 1, , p. 114-133 (DOI 10.1145/322234.322243).
- (en) La classe EXPTIME sur le Complexity Zoo.
- (en) Chris Umans, « CS21 Decidability and Tractability (Lecture 16-17) » [PDF], sur Caltech, .
- (en) « A near-optimal method for reasoning about action », Journal of Computer and System Sciences, vol. 20, no 2, , p. 231–254 (ISSN 0022-0000, DOI 10.1016/0022-0000(80)90061-6, lire en ligne, consulté le ).
- (en) L. Stockmeyer et A. Chandra, « Provably Difficult Combinatorial Games », SIAM Journal on Computing, vol. 8, no 2, , p. 151–174 (ISSN 0097-5397, DOI 10.1137/0208013, lire en ligne, consulté le ).
- (en) Aviezri Fraenkel et D. Lichtenstein, « Computing a perfect strategy for n×n chess requires time exponential in n », J. Comb. Th. A, no 31, , p. 199-214.
- (en) J. M. Robson, « N by N checkers is Exptime complete », SIAM Journal on Computing, vol. 13, no 2, , p. 252-267 (DOI 10.1137/0213018).
- (en) J. M. Robson, « The complexity of Go », dans Information Processing; Proceedings of IFIP Congress, , p. 413-417.
- (en) Robert Aubrey Hearn, Games, puzzles, and computation (thèse de doctorat), (lire en ligne).
- Michael L. Littman, « Probabilistic Propositional Planning: Representations and Complexity », In Proceedings of the Fourteenth National Conference on Artificial Intelligence, MIT Press, , p. 748–754 (lire en ligne, consulté le )
Voir aussi
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]- 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.
Liens externes
[modifier | modifier le code]
