classe de complexité De Wikipédia, l'encyclopédie libre
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.
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.
Le problème de l'accessibilité (aussi appelé s-t-accessibilité) qui consiste, étant donné un graphe orienté G, et deux sommets s et t de G, à déterminer s'il y a un chemin de s à t dans G, est NL-complet. Dans ce problème, le graphe est représenté explicitement, avec une matrice d'adjacence ou avec des listes d'adjacences.
Voici d'autres problèmes de décision NL-complets :
En 1976, Neil D. Jones, Y. Edmund Lien et William T. Laaser propose des démonstrations de NL-complétude pour plusieurs problèmes[7], à l'instar des problèmes de Karp pour la NP-complétude.
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, c'est-à-dire que L NL. Au , l'autre sens NL L est un problème ouvert. Un autre résultat est donné par le théorème de Savitch[8] :
Théorème de Savitch —
Un autre résultat est le théorème dû à Neil Immerman[9] et Róbert Szelepcsényi[10] indépendamment :
Théorème d'Immerman-Szelepcsényi — , pour toute fonction , en particulier NL=co-NL
La classe NL est incluse dans NC, même plus précisément dans NC2[11]. Pour le démontrer, on construit un circuit de taille polynomiale et de profondeur polylogarithmique pour le problème d'accessibilité qui est NL-complet. On montre aussi que la classe NC est stable par réduction logarithmique.
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[12].
En complexité descriptive, NL correspond à la logique du premier ordre avec fermeture transitive[13].
Seamless Wikipedia browsing. On steroids.