En la teoría de la complejidad computacional , NL-completo es una clase de complejidad que contiene los lenguajes que están completos para NL , la clase de problemas de decisión que puede resolver 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 método para la solución de uno cualquiera de los problemas NL-completos en el espacio de memoria logarítmica, a continuación, NL = L .
Definiciones
NL consiste en los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista con una cinta de entrada de solo lectura y una cinta de lectura-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 los mismos supuestos sobre la longitud de la cinta. Debido a que solo hay un número polinomial 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 polinomial.
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.
Propiedades
Si un lenguaje X completo de NL podría pertenecer a L , entonces también lo serían todos los demás idiomas Y en NL . Por ejemplo , suponga (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 el supuesto de que X está en L ) que existe una logspace algoritmo a para la resolución de problemas X . Con estos supuestos, 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 ).
Se deduce del teorema de Immerman-Szelepcsényi que, si un lenguaje es co-NL-completo (es decir, si su complemento es NL-completo), entonces el lenguaje también es NL-completo en sí mismo.
Ejemplos de
Un problema NL-completa importante es 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 gráfico, hay un camino de s a t . ST-conectividad puede ser visto como en NL , porque empezamos en el nodo s y nondeterministically caminamos a todos los demás nodos alcanzables. Se puede ver que la conectividad ST es NL-hard al considerar el gráfico de estado de cálculo de cualquier otro algoritmo NL , y considerando que el otro algoritmo aceptará si y solo si hay una ruta (no determinista) desde el estado inicial a un estado de aceptación .
Otro problema importante de NL-completo es 2-satisfacebilidad (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 satisfactoria.
Rytter (1986) demostró que el problema de la descifrabilidad única de un código de longitud variable dado era co-NL-completo ; Rytter utilizó una variante del algoritmo de Sardinas-Patterson para mostrar que el problema complementario, encontrar una cadena que tiene múltiples decodificaciones ambiguas, pertenece a NL . Debido al teorema de Immerman-Szelepcsényi, se deduce que la descifrabilidad única también es NL-completa.
Los problemas adicionales-NL completa en Lógica Proposicional , Algebra, Sistema lineal, Gráfico, autómatas finitos , libre de contexto Gramática se enumeran en Jones (1976).
Referencias
- Papadimitriou, Christos H. (1994). Complejidad computacional . Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.
- Rytter, Wojciech (1986), "La complejidad espacial del problema de descifrabilidad única", Information Processing Letters , 23 (1): 1-3, doi : 10.1016 / 0020-0190 (86) 90121-3 , MR 0853618.
- Jones, Neil D .; Lien, Y. Edmund; Laaser, William T (1976). "Nuevos problemas completos para espacio de registro no determinista". Teoría de sistemas matemáticos . 10 (1): 1–17. doi : 10.1007 / BF01683259 .