E (complexité) - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for E (complexité).

E (complexité)

Un article de Wikipédia, l'encyclopédie libre.

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 de la classe E, une machine de Turing opérant en temps pour un , de sorte que tout mot est accepté, par la machine , en au plus pas de calcul.

Si l'on appelle DTIME, l'ensemble des problèmes qui peuvent être résolus par des machine de Turing déterministes utilisant un temps pour une fonction en la taille de l'entrée , alors on a[1]

E = DTIME.

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

EXPTIME =

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

PSPACEE.

Alors que pour EXPTIME, on a l'inclusion :

PSPACE EXPTIME,

aucune relation entre E et PSPACE n'est connue.

Propriétés

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

Notes et références

  1. (en) La classe E sur le Complexity Zoo
  2. Book 1972.
  3. Book 1974.
  4. Impagliazzo et Tardos 1989.
  5. Pour une notion de mesure détaillée par Allender et Strauss.
  6. Allender et Strauss 1994.

Bibliographie

  • Eric Allender et Martin Strauss, « Measure on small complexity classes with applications for BPP », Proceedings of IEEE FOCS,‎ , p. 807–818 (présentation en ligne).
  • Ron Book, « On languages accepted in polynomial time », SIAM Journal on Computing, vol. 1, no 4,‎ , p. 281–287 (DOI 10.1137/0201019).
  • Ron Book, « Comparing complexity classes », Journal of Computer and System Sciences, vol. 3, no 9,‎ , 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,‎ , p. 222–227.
  • Osamu Watanabe, « Comparison of polynomial time completeness notions », Theoretical Computer Science, vol. 54,‎ , p. 249–265 (DOI 10.1016/0304-3975(87)90132-0).
{{bottomLinkPreText}} {{bottomLinkText}}
E (complexité)
Listen to this article