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

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

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

NEXPTIME = ${\displaystyle \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^[1]

P^NE = NP^NE,

résultat établi en 1989^[2].

Liens externes

• (en) La classe E sur le Complexity Zoo

Notes et références

1. (en) La classe NE sur le Complexity Zoo
2. L. Hemachandra, « The strong exponential hierarchy collapses », Journal of Computer and System Sciences, vol. 39, n^o 3,‎ 1989, p. 299-322.

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