NL (complexité)

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

NL est une classe de complexité, un objet de la théorie de la complexité (un domaine de l'informatique théorique). Cette classe est aussi appelée NLogSpace.

C'est l'ensemble des problèmes qui peuvent être décidés par des machines de Turing non-déterministes dont l'espace de travail est bornée par une fonction logarithmique.

Définition formelle[modifier | modifier le code]

Si l'on appelle \mbox{NSPACE}(t(n)), l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing non-déterministes utilisant un espace O(t(n)) pour une fonction t en la taille de l'entrée n, alors on peut définit NL formellement par :

\mbox{NL} = \mbox{NSPACE}(log(n)) \ .

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\scriptstyle\subseteq P.

Comme pour toutes les classes la variante non-déterministe contient la version déterministe, on a donc L\scriptstyle\subseteqNL. Un résultat dans l'autre sens, est donné par le théorème de Savitch:

\mathbf{NL \subseteq SPACE}(\log^2 n)

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

Théorème d'Immerman-Szelepcsényi —  \text{NSPACE}(s(n))=\text{co-NSPACE}(s(n)), pour toute fonction s(n)\geq\log n, en particulier NL=co-NL

Problèmes NL-complets[modifier | modifier le code]

Un problème complet de NL (pour les réductions log-space) est le problème de l'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 ?

Un autre est 2-SAT, la restriction du problème SAT (qui est NP-complet) aux 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,‎ 2009 (ISBN 0-521-42426-7), chap. 4 (« Space complexity »)

Lien externe[modifier | modifier le code]

(en) La classe NL sur le Complexity Zoo