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 [1].

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[2] :

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 :

Autres définitions[modifier | modifier le code]

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

Une définition par certificat est aussi possible, comme pour NP. Les contraintes à ajouter sont les suivantes : le vérificateur est unidirectionnel, c'est-à-dire que la tête de lecture ne peut pas revenir en arrière, et il travaille en espace logarithmique[3].

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

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

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

  1. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.3 (« Considérations de base sur l’espace : comparaison avec les classes en temps »), p. 109
  2. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5.2 (« Théorème de Savitch »), p. 118.
  3. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5.1 (« Certificats unidirectionnels »), p. 117.
  4. (en) Neil Immerman, « Languages Which Capture Complexity Classes », 15th ACM STOC Symp.,‎ , p. 347-354 (lire en ligne).

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