Accueil🇫🇷Chercher

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

PNE = NPNE,
résultat établi en 1989[2].

Liens externes

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, no 3,‎ , p. 299-322.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.