2 Définitions et Propriétés
2.1 EXPTIME
La définition de la classe EXPTIME est :
où DTIME représente le temps que prendrait un ordinateur pour résoudre un problème de décision avec une entrée de taille n, sans limite de mémoire.
On a la hiérarchie de classe suivante : 
NEXPTIME correspond, par analogie à NP, à l’ensemble des problèmes décidables par une machine de Turing non-déterministe en un temps exponentiel.
2.2 EXPTIME-complet
Un problème est dit EXPTIME-complet s’il appartient à EXPTIME et si tous les problèmes EXPTIME peuvent être réduits en temps polynomial vers lui. Une réduction est la transformation d’un problème vers un autre, notamment afin de résoudre le premier.
Les problèmes EXPTIME-complets sont considérés comme les plus difficiles de la classe EXPTIME. De plus, nous savons que les problèmes EXPTIME-complets ne sont pas dans P, c'est-à-dire qu’ils ne peuvent pas être résolus en temps polynomial.
- AurelienGasser
- 00:55
- > Lien permanent
- > Commentaires
- > Abus ?
