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. 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 . 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. vignette|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. décider si le langage d'un automate fini déterministe (avec un alphabet non unaire) est vide. Si l'alphabet est unaire, le problème devient L-complet. décider si le langage d'un automate fini déterministe est le langage de tous les mots (attention, si l'automate fini est non-déterministe, le problème devient PSPACE-complet). décider si le langage d'un automate de Büchi est vide est NL-complet. En 1976, Neil D. Jones, Y. Edmund Lien et William T. Laaser propose des démonstrations de NL-complétude pour plusieurs problèmes, à 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.