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.

Liens externes

• (en) La classe E sur le Complexity Zoo

Notes et références

• (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).

Bibliographie

• 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).