En la teoría de la complejidad computacional , NL-completa es una clase de complejidad que contiene los lenguajes que son completos para NL , la clase de problemas de decisión que pueden resolverse mediante una máquina de Turing no determinista utilizando una cantidad logarítmica de espacio de memoria . Los lenguajes completos de NL son los problemas más "difíciles" o "expresivos" de NL . Si existe un algoritmo determinista para resolver cualquiera de los problemas NL-completos en el espacio de memoria logarítmica, entonces NL = L.
NL consta de problemas de decisión que pueden resolverse mediante una máquina de Turing no determinista con una cinta de entrada de sólo 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 lenguajes que pueden resolverse mediante una máquina de Turing determinista con los mismos supuestos sobre la longitud de la cinta. Debido a que sólo hay un número polinómico de configuraciones distintas de estas máquinas, tanto L como NL son subconjuntos de la clase P de problemas deterministas de decisión en tiempo polinomial.
Formalmente, un problema de decisión es NL completo cuando pertenece a NL y tiene la propiedad adicional de que todos los demás problemas de decisión en NL pueden 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 X completo en NL pudiera pertenecer a L , entonces también lo harían todos los demás idiomas Y en NL . Porque, supongamos (por completitud NL) que existiera una reducción determinista en el espacio logarítmico r que mapea una instancia y del problema Y a una instancia x del problema X , y también (mediante el supuesto de que X está en L ) que existe una reducción determinista en el espacio logarítmico r. Algoritmo de espacio logístico A para resolver el problema X. Con estos supuestos, un problema y en el lenguaje Y podría resolverse en espacio logarítmico mediante un algoritmo que simule el comportamiento del algoritmo A en la entrada r ( y ), utilizando el algoritmo de reducción para simular cada acceso a la cinta de sólo lectura para r ( y ).
Del teorema de Immerman-Szelepcsényi se deduce que, si una lengua es co-NL-completa (es decir, si su complemento es NL-completo), entonces la lengua también es NL-completa.
Un problema importante de NL completo es la conectividad ST (o "alcanzabilidad") (Papadimitriou 1994 Thrm. 16.2), el problema de determinar si, dado un gráfico dirigido G y dos nodos s y t en ese gráfico, hay un camino desde s a t . Se puede ver que la conectividad ST está en NL , porque comenzamos en los nodos s y caminamos de manera no determinista hasta todos los demás nodos alcanzables. Se puede ver que la conectividad ST es NL-difícil al considerar el gráfico de estado de cálculo de cualquier otro algoritmo NL , y considerar que el otro algoritmo aceptará si y solo si hay una ruta (no determista) desde el estado inicial hasta un estado de aceptación. .
Otro problema importante de NL completo es la 2-satisfabilidad (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 satisfactible.
Rytter (1986) demostró que el problema de la descifrabilidad única de un código dado de longitud variable es co-NL-completo; Rytter utilizó una variante del algoritmo de Sardinas-Patterson para demostrar que el problema complementario, encontrar una cadena que tenga múltiples decodificaciones ambiguas, pertenece a NL . Debido al teorema de Immerman-Szelepcsényi, se deduce que la descifrabilidad única también es completa en NL.
En Jones (1976) se enumeran problemas adicionales completos de NL sobre lógica proposicional , álgebra, sistema lineal, gráficos, autómatas finitos y gramática libre de contexto .