NE (complexité)

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).}$

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

• (en) La classe E sur le Complexity Zoo