NL (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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é : savoir s'il y a un chemin d'une source s à un sommet destination t.

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'une 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]

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, 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]

  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. « Examen qui pose cette question »
  3. a b c et d « 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 13 décembre 2017)
  4. « 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 13 décembre 2017)
  5. 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)
  6. (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 7 février 2020) :

    « Theorem 2.9 The nonemptiness problem for Büchi automata is logspace complete for NLOGSPACE. »

  7. (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 7 novembre 2018)
  8. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5.2 (« Théorème de Savitch »), p. 118.
  9. 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 7 février 2020)
  10. (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 7 février 2020)
  11. (en) Papadimitriou, Computational complexity, Theorem 16.1 (p. 395)
  12. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5.1 (« Certificats unidirectionnels »), p. 117.
  13. (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