title: E (complexité)
text: # 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.
  