E (complexité)
# E (complexité)

En informatique théorique et notamment en théorie de la complexité, la classe E est une classe de complexité ; c'est l'ensemble des problèmes de décision qui peuvent être décidés par une machine de Turing déterministe en temps exponentiel avec un exposant linéaire.

## Définition formelle

Formellement, il existe, pour tout langage $L$ de la classe E, une machine de Turing $M_{L}$ opérant en temps $t_{L}(n)\in O(k^{n})$ pour un $k\in \mathbb {N}$, de sorte que tout mot $w\in L$ est accepté, par la machine $M_{L}$, en au plus $t_{L}(|w|)$ pas de calcul.

Si l'on appelle DTIME$(t(n))$, l'ensemble des 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 a

    E = DTIME$(2^{O(n)})$.

Ainsi, E est une des composantes de EXPTIME qui est formellement définie par :

    EXPTIME = $\bigcup _{k\in \mathbb {N} }{\text{DTIME}}\left(2^{n^{k}}\right).$

La classe E joue un rôle important en théorie de la complexité dans la mesure où elle n'est pas, contrairement à EXPTIME close par réduction polynomiale. Il en résulte que

    PSPACE ≠ E.

Alors que pour EXPTIME, on a l'inclusion :

    PSPACE $\subseteq$ EXPTIME,

aucune relation entre E et PSPACE n'est connue.

## Propriétés

* La classe E est différente de NP ou PSPACE relativement à tout oracle. Toutefois, il existe un oracle pour lequel E est contenue dans NP, et un oracle pour lequel PSPACE est contenu dans E.
* Il existe un oracle pour lequel E = NE, mais il existe une prédicat binaire de complexité exponentielle en temps, pour lequel le problème de recherche correspondant n’est pas dans la classe n'est pas dans E.
* Les problèmes difficiles de la classe BPP sont de mesure 1 dans la classe E. Il en résulte que si les problèmes complets de la classe E ne sont pas de mesure 1 dans E, alors BPP n'est pas égale à EXPTIME.
