En la teoría de la complejidad computacional , NL-completo es una clase de complejidad que contiene los lenguajes que son completos para NL , la clase de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista utilizando una cantidad logarítmica de espacio de memoria . Los lenguajes NL-completos son los problemas más "difíciles" o "expresivos" en NL . Si existe un algoritmo determinista para resolver cualquiera de los problemas NL-completos en el espacio de memoria logarítmico, entonces NL = L.
NL consta de los problemas de decisión que pueden resolverse mediante una máquina de Turing no determinista con una cinta de entrada de solo lectura y una cinta de lectura y escritura separada cuyo tamaño está limitado a ser proporcional al logaritmo de la longitud de entrada. De manera similar, L consta de los lenguajes que pueden resolverse mediante una máquina de Turing determinista con las mismas suposiciones sobre la longitud de la cinta. Debido a que solo existe un número polinómico de configuraciones distintas de estas máquinas, tanto L como NL son subconjuntos de la clase P de problemas de decisión deterministas de tiempo polinómico.
Formalmente, un problema de decisión es NL-completo cuando pertenece a NL y tiene la propiedad adicional de que cualquier otro problema de decisión en NL puede reducirse a él. A menos que se especifique lo contrario, se supone que las reducciones en esta definición son reducciones de muchos-uno mediante un algoritmo determinista de espacio logarítmico.
Si un lenguaje NL-completo X pudiera pertenecer a L , entonces también lo haría cualquier otro lenguaje Y en NL . Pues, supongamos (por NL-completitud) que existiera una reducción determinista del espacio logarítmico r que mapea una instancia y del problema Y a una instancia x del problema X , y también (por la suposición de que X está en L ) que existe un algoritmo determinista del espacio logarítmico A para resolver el problema X . Con estas suposiciones, un problema y en el lenguaje Y podría resolverse en el espacio logarítmico mediante un algoritmo que simula el comportamiento del algoritmo A en la entrada r ( y ), utilizando el algoritmo de reducción para simular cada acceso a la cinta de solo lectura para r ( y ).
Del teorema de Immerman-Szelepcsényi se desprende que, si una lengua es co-NL-completa (es decir, si su complemento es NL-completa), entonces la lengua también es NL-completa en sí misma.
Un problema importante de NL-completo es la ST-conectividad (o "Alcanzabilidad") (Papadimitriou 1994 Thrm. 16.2), el problema de determinar si, dado un grafo dirigido G y dos nodos s y t en ese grafo, hay un camino desde s hasta t . La ST-conectividad se puede ver como en NL , porque comenzamos en el nodo s y caminamos de manera no determinista a cada uno de los otros nodos alcanzables. La ST-conectividad se puede ver como NL-hard al considerar el grafo de estados de cómputo de cualquier otro algoritmo NL , y considerando que el otro algoritmo aceptará si y solo si hay un camino (no determinista) desde el estado inicial a un estado de aceptación.
Otro problema NL-completo importante es la 2-satisfacibilidad (Papadimitriou 1994 Thrm. 16.3), el problema de determinar si una fórmula booleana en forma normal conjuntiva con dos variables por cláusula es satisfacible.
Rytter (1986) demostró que el problema de la descifrabilidad única de un código de longitud variable dado es co-NL-completo; Rytter utilizó una variante del algoritmo Sardinas-Patterson para demostrar que el problema complementario, encontrar una cadena que tenga múltiples descodificaciones ambiguas, pertenece a NL . Debido al teorema de Immerman-Szelepcsényi, se deduce que la descifrabilidad única también es NL-completa.
En Jones (1976) se enumeran problemas NL-completos adicionales sobre lógica proposicional , álgebra, sistemas lineales, gráficos, autómatas finitos y gramática libre de contexto .