NL (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, plus précisément en théorie de la complexité, NL est une classe de complexité. Cette classe est aussi appelée NLogSpace[réf. nécessaire]. C'est l'ensemble des problèmes de décision qui peuvent être décidés par des machines de Turing non déterministes dont l'espace de travail est borné par une fonction logarithmique.

Définition formelle[modifier | modifier le code]

Si l'on appelle , l'ensemble des problèmes de décision qui peuvent être décidés par des machines de Turing non déterministes utilisant un espace pour une fonction en la taille de l'entrée , alors on définit .

Un problème A est NL-dur si tout problème de NL se réduit en espace logarithmique à A. Un problème est NL-complet s'il est dans NL et NL-dur.

Relations avec les autres classes[modifier | modifier le code]

Représentations des inclusions des classes usuelles

La classe NL est une classe relativement petite parmi les classes usuelles. On a notamment NL P.

Comme pour toutes les classes, la variante non déterministe contient la version déterministe, on a donc LNL. Au 1er janvier 2015, l'autre sens NL L est un problème ouvert. Un autre résultat est donné par le théorème de Savitch :

Un autre résultat est le théorème dû à Neil Immerman et Róbert Szelepcsényi :

Théorème d'Immerman-Szelepcsényi —  , pour toute fonction , en particulier NL=co-NL

Exemples de problèmes NL-complets[modifier | modifier le code]

Les problèmes de décision suivants sont NL-complets :

  • le problème de l'accessibilité (aussi appelé s-t-accessibilité) : étant donné un graphe orienté G, et deux sommets s et t de G, y a-t-il un chemin de s à t dans G ?
  • 2-SAT, la restriction du problème SAT (qui est NP-complet) aux ensembles de clauses d'au plus deux littéraux.

Autres définitions[modifier | modifier le code]

Définition par certificat[modifier | modifier le code]

Définition probabiliste[modifier | modifier le code]

Définition de complexité descriptive[modifier | modifier le code]

En complexité descriptive, NL correspond à la logique du premier ordre avec fermeture transitive.

Notes et références[modifier | modifier le code]


Bibliographie[modifier | modifier le code]

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 4 (« Space complexity »)

Lien externe[modifier | modifier le code]

(en) La classe NL sur le Complexity Zoo