1 Introduction

La classe EXPTIME fait partie des classes d’algorithmes introduites par la théorie de la complexité. Cette théorie s’intéresse notamment à l’efficacité de la résolution en temps et en mémoire d’un algorithme en fonction de la taille de son entrée. On utilise généralement une machine de Turing pour représenter l’appareil de calcul.

Ainsi, EXPTIME rassemble les problèmes décidables par une machine de Turing déterministe en  avec p polynôme, soit en un temps exponentiel par rapport à la taille de son entrée.

Nous introduirons dans une première partie les propositions importantes d’EXPTIME, puis nous présenterons des problèmes connus.