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.

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

Si l'on appelle DTIME${\displaystyle (t(n))}$, l'ensemble des problèmes qui peuvent être résolus par des machines de Turing déterministes utilisant un temps ${\displaystyle O(t(n))}$ pour une fonction ${\displaystyle t}$ en la taille de l'entrée ${\displaystyle n}$, alors on a^[1]

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

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

EXPTIME = ${\displaystyle \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 ${\displaystyle \subseteq }$ EXPTIME,

aucune relation entre E et PSPACE n'est connue.

• La classe E est différente de NP^[2] ou PSPACE^[3] 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^[4], 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^[5] 1 dans la classe E^[6]. 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.

• (en) La classe E sur le Complexity Zoo

• (de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « E (Komplexitätsklasse) » (voir la liste des auteurs).

• Eric Allender et Martin Strauss, « Measure on small complexity classes with applications for BPP », Proceedings of IEEE FOCS,‎ 1994, p. 807–818 (présentation en ligne).
• Ron Book, « On languages accepted in polynomial time », SIAM Journal on Computing, vol. 1, n^o 4,‎ 1972, p. 281–287 (DOI 10.1137/0201019).
• Ron Book, « Comparing complexity classes », Journal of Computer and System Sciences, vol. 3, n^o 9,‎ 1974, p. 213–229 (DOI 10.1016/s0022-0000(74)80008-5).
• Russell Impagliazzo et Gábor Tardos, « Decision versus search problems in super-polynomial time », Proceedings of IEEE FOCS,‎ 1989, p. 222–227.
• Osamu Watanabe, « Comparison of polynomial time completeness notions », Theoretical Computer Science, vol. 54,‎ 1987, p. 249–265 (DOI 10.1016/0304-3975(87)90132-0).

• Portail des mathématiques
• Portail de l'informatique théorique