NL (complexité)
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.
Exemples de problèmes NL-complets[modifier | modifier le code]
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 :
- 2-SAT, la restriction du problème SAT (qui est NP-complet) aux ensembles de clauses d'au plus deux littéraux.
- décider si le langage d'un automate fini non-déterministe est vide[2],[3],[4].
- décider si le langage d'un automate fini déterministe (avec un alphabet non unaire) est vide[3]. Si l'alphabet est unaire, le problème devient L-complet[3].
- décider si le langage d'un automate fini déterministe est le langage de tous les mots[3] (attention, si l'automate fini est non-déterministe, le problème devient PSPACE-complet[5]).
- décider si le langage d'un automate de Büchi est vide est NL-complet[6].
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.
Relations avec les autres classes[modifier | modifier le code]
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.
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[12].
Définition de complexité descriptive[modifier | modifier le code]
En complexité descriptive, NL correspond à la logique du premier ordre avec fermeture transitive[13].
Notes et références[modifier | modifier le code]
- 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
- « Examen qui pose cette question »
- « Space-bounded reducibility among combinatorial problems », Journal of Computer and System Sciences, vol. 11, no 1, , p. 68–85 (ISSN 0022-0000, DOI 10.1016/S0022-0000(75)80050-X, lire en ligne, consulté le )
- « Complexity of universality and related problems for partially ordered NFAs », Information and Computation, vol. 255, , p. 177–192 (ISSN 0890-5401, DOI 10.1016/j.ic.2017.06.004, lire en ligne, consulté le )
- Alfred V. Aho et John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., (ISBN 0201000296, lire en ligne)
- (en) A. Prasad Sistla, Moshe Y. Vardi et Pierre Wolper, « The complementation problem for Büchi automata with applications to temporal logic », Theoretical Computer Science, vol. 49, no 2, , p. 217–237 (ISSN 0304-3975, DOI 10.1016/0304-3975(87)90008-9, lire en ligne, consulté le ) :
« Theorem 2.9 The nonemptiness problem for Büchi automata is logspace complete for NLOGSPACE. »
- (en) Neil D. Jones, Y. Edmund Lien et William T. Laaser, « New problems complete for nondeterministic log space », Mathematical Systems Theory, vol. 10, no 1, , p. 1–17 (ISSN 0025-5661 et 1433-0490, DOI 10.1007/bf01683259, lire en ligne, consulté le )
- Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5.2 (« Théorème de Savitch »), p. 118.
- Neil. Immerman, « Nondeterministic Space is Closed under Complementation », SIAM Journal on Computing, vol. 17, no 5, , p. 935–938 (ISSN 0097-5397, DOI 10.1137/0217058, lire en ligne, consulté le )
- (en) Róbert Szelepcsényi, « The method of forced enumeration for nondeterministic automata », Acta Informatica, vol. 26, no 3, , p. 279–284 (ISSN 1432-0525, DOI 10.1007/BF00299636, lire en ligne, consulté le )
- (en) Papadimitriou, Computational complexity, Theorem 16.1 (p. 395)
- Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5.1 (« Certificats unidirectionnels »), p. 117.
- (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 »)
