NE (complexité) - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for NE (complexité).

NE (complexité)

Un article de Wikipédia, l'encyclopédie libre.

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

Notes et références

  1. a et b (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.
{{bottomLinkPreText}} {{bottomLinkText}}
NE (complexité)
Listen to this article