NE (complexité)

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

Formellement, il existe, pour tout langage $L$ de la classe NE, une machine de Turing $M_{L}$ non déterministe 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 NTIME$(t(n))$, l'ensemble des problèmes qui peuvent être résolus par des machines de Turing non déterministes en temps $O(t(n))$ pour une fonction $t$ en la taille de l'entrée $n$, alors on a

NE = NTIME$(2^{O(n)})$.

Ainsi, NE est une des composantes de NEXPTIME qui est formellement définie par :

NEXPTIME = $\bigcup _{k\in \mathbb {N} }{\text{NTIME}}\left(2^{n^{k}}\right).$

Propriétés

• 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

P^NE = NP^NE,

résultat établi en 1989.

Liens externes

• (en) La classe E sur le Complexity Zoo