NL (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique théorique
Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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