EXPTIME

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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]

Diagramme d'inclusions des classes de complexité classiques

Comme l'illustre l'image de droite, on a les inclusions suivantes : 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, P 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]

Jeu PEEK, un des premiers jeux à deux joueurs démontré EXPTIME-complet par Chandra et Stockmeyer

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)[réf. nécessaire].

Des versions succinctes de problèmes P-complets sont EXPTIME-complet, comme par exemple 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 à deux joueurs et des jeux sur des graphes qui sont EXPTIME-complets[5]. Un des jeux booléens, EXPTIME-complet, est présenté comme un jeu à deux joueurs appelé PEEK. Une boîte est perforé 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 des 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).

Les travaux de Chandra Stockmeyer ont alors permis de montrer que des versions généralisées de jeux, comme les échecs[6], les dames[7] et le go[8] 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.

Article lié[modifier | modifier le code]

  • 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]

Notes et références[modifier | modifier le code]

  1. (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 »)
  2. 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)
  3. (en) La classe EXPTIME sur le Complexity Zoo
  4. (en) Chris Umans, « CS21 Decidability and Tractability (Lecture 16-17) », sur Caltech, .
  5. 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)
  6. (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.
  7. (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).
  8. (en) J. M. Robson, « The complexity of Go », dans Information Processing; Proceedings of IFIP Congress, , p. 413-417.