EXPTIME

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

EXPTIME (ou EXP) est une classe de complexité, c'est-à-dire un ensemble de problèmes de décision utilisé en théorie de la complexité.

Plus précisément, c'est l'ensemble des problèmes de décision qui peuvent se résoudre sur une machine de Turing déterministe en temps exponentiel.

Définition formelle[modifier | modifier le code]

Si l'on appelle \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 O(t(n)) pour une fonction t en la taille de l'entrée n, alors on peut définir EXPTIME formellement par :

 \mbox{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ n^k } \right) .

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 \scriptstyle\subseteq PSPACE \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 (en) et NEXPTIME (en) (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 EXPTIME\scriptstyle\neqNEXPTIME alors P\scriptstyle\neqNP

De plus d'après le théorème de hiérarchie en temps (en), P \scriptstyle\subsetneq EXPTIME.

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

En complexité descriptive, EXPTIME correspond à SO(LFP) (logique d'ordre 2 avec plus petit point fixe)[3].

Problèmes EXPTIME-complets[modifier | modifier le code]

Un problème complet pour EXPTIME est le problème de l'arrêt d'une machine de Turing après k pas de temps[4]. C'est une restriction du problème de l'arrêt, qui est indécidable dans le cas général.

D'autre problème EXPTIME complet sont des variantes de jeux, comme les échecs[5], les dames[6] et le go[7].

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,‎ 2009 (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,‎ 1981, p. 114-133 (lien DOI?)
  3. (en) La classe EXPTIME sur le Complexity Zoo
  4. (en) Chris Umans, « Support du cours CS 21 (Lecture 18) »
  5. Aviezri Fraenkel (en) et D. Lichtenstein, « Computing a perfect strategy for n×n chess requires time exponential in n », J. Comb. Th. A, no 31,‎ 1981, p. 199-214
  6. J. M. Robson, « N by N checkers is Exptime complete », SIAM Journal on Computing, vol. 13, no 2,‎ 1984, p. 252-267 (lien DOI?)
  7. J. M. Robson, « The complexity of Go », dans Information Processing; Proceedings of IFIP Congress,‎ 1983, p. 413-417.