NE (complexité) — Wikipédia
En informatique théorique et notamment en théorie de la complexité, la classe NE 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 non déterministe en temps exponentiel avec un exposant linéaire. C'est une classe de complexité d'importance mineure.
Définition formelle
[modifier | modifier le code]Formellement, il existe, pour tout langage de la classe NE, une machine de Turing non déterministe 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 NTIME, l'ensemble des problèmes qui peuvent être résolus par des machines de Turing non déterministes en temps pour une fonction en la taille de l'entrée , alors on a[1]
- NE = NTIME.
Ainsi, NE est une des composantes de NEXPTIME qui est formellement définie par :
- NEXPTIME =
Propriétés
[modifier | modifier le code]- La classe NE a la propriété de ne pas être, contrairement à NEXPTIME, close par réduction polynomiale.
- La classe NE, utilisée oracle, fait collapser les classes P et NP ; avec les notations pour les oracles, on a[1]
- PNE = NPNE,
- résultat établi en 1989[2].
Liens externes
[modifier | modifier le code]Notes et références
[modifier | modifier le code]- (en) La classe NE sur le Complexity Zoo
- L. Hemachandra, « The strong exponential hierarchy collapses », Journal of Computer and System Sciences, vol. 39, no 3, , p. 299-322.