En la teoría de la complejidad computacional , NL ( espacio logarítmico no determinista) es la clase de complejidad que contiene problemas de decisión que pueden resolverse mediante una máquina de Turing no determinista utilizando una cantidad logarítmica de espacio de memoria .
NL es una generalización de L , la clase para problemas de espacio logarítmico en una máquina determinista de Turing . Dado que cualquier máquina de Turing determinista es también una máquina de Turing no determinista , tenemos que L está contenido en NL .
NL se puede definir formalmente en términos del espacio no determinista de recursos computacionales (o NSPACE) como NL = NSPACE (log n ).
Resultados importantes en la teoría de la complejidad nos permiten relacionar esta clase de complejidad con otras clases, lo que nos informa sobre el poder relativo de los recursos involucrados. Los resultados en el campo de los algoritmos , por otro lado, nos dicen qué problemas se pueden resolver con este recurso. Como gran parte de la teoría de la complejidad, muchas cuestiones importantes sobre la NL aún están abiertas (ver Problemas no resueltos en informática ).
Ocasionalmente, se hace referencia a NL como RL debido a su definición probabilística a continuación; sin embargo, este nombre se utiliza con más frecuencia para referirse al espacio logarítmico aleatorio , que no se sabe que sea igual a NL .
Se sabe que varios problemas son NL completos bajo reducciones de espacio logarítmico , incluida la conectividad ST y la satisfacibilidad 2 . La conectividad ST pregunta, para los nodos S y T en un gráfico dirigido , si T es accesible desde S. La 2-satisfacibilidad pregunta, dada una fórmula proposicional en la que cada cláusula es la disyunción de dos literales, si existe una asignación variable que haga que la fórmula sea verdadera. Un ejemplo de ejemplo, donde indica no , podría ser:
Se sabe que NL está contenido en P , ya que existe un algoritmo de tiempo polinómico para la satisfacibilidad 2 , pero no se sabe si NL = P o si L = NL . Se sabe que NL = co-NL , donde co-NL es la clase de lenguas cuyos complementos están en NL . Este resultado (el teorema de Immerman-Szelepcsényi ) fue descubierto de forma independiente por Neil Immerman y Róbert Szelepcsényi en 1987; Recibieron el Premio Gödel en 1995 por este trabajo.
En la complejidad del circuito , NL se puede colocar dentro de la jerarquía NC . En Papadimitriou 1994, Teorema 16.1, tenemos:
Más precisamente, NL está contenido en AC 1 . Se sabe que NL es igual a ZPL , la clase de problemas que se pueden resolver mediante algoritmos aleatorios en espacio logarítmico y tiempo ilimitado, sin error. Sin embargo, no se sabe ni se cree que sea igual a RLP o ZPLP , las restricciones de tiempo polinomial de RL y ZPL , a las que algunos autores se refieren como RL y ZPL .
Podemos relacionar NL con el espacio determinista usando el teorema de Savitch , que nos dice que cualquier algoritmo no determinista puede ser simulado por una máquina determinista en un espacio cuadráticamente mayor como máximo. Del teorema de Savitch tenemos directamente que:
Esta fue la inclusión de espacio determinista más fuerte conocida en 1994 (Papadimitriou 1994 Problema 16.4.10, "Espacio simétrico"). Dado que las clases espaciales más grandes no se ven afectadas por aumentos cuadráticos, se sabe que las clases no deterministas y deterministas son iguales, de modo que, por ejemplo, tenemos PSPACE = NPSPACE .
Supongamos que C es la clase de complejidad de problemas de decisión que se pueden resolver en un espacio logaritmítico con máquinas probabilísticas de Turing que nunca aceptan incorrectamente pero se les permite rechazar incorrectamente menos de 1/3 de las veces; esto se llama error unilateral . La constante 1/3 es arbitraria; cualquier x con 0 ≤ x < 1/2 sería suficiente.
Resulta que C = NL . Observe que C , a diferencia de su contraparte determinista L , no se limita al tiempo polinómico, porque aunque tiene un número polinómico de configuraciones, puede usar la aleatoriedad para escapar de un bucle infinito. Si lo limitamos al tiempo polinómico, obtenemos la clase RL , que está contenida en NL , pero no se sabe ni se cree que sea igual .
Existe un algoritmo sencillo que establece que C = NL . Claramente C está contenido en NL , ya que:
Para mostrar que NL está contenido en C , simplemente tomamos un algoritmo de NL y elegimos una ruta de cálculo aleatoria de longitud n , y ejecutamos esto 2 n veces. Debido a que ninguna ruta de cálculo excede la longitud n , y debido a que hay 2 n rutas de cálculo en total, tenemos una buena posibilidad de encontrar la que acepta (limitada a continuación por una constante).
El único problema es que no tenemos espacio en el espacio de registro para un contador binario que llegue hasta 2 n . Para solucionar esto, lo reemplazamos con un contador aleatorio , que simplemente lanza n monedas y se detiene y rechaza si todas caen en cara. Dado que este evento tiene una probabilidad de 2 − n , esperamos dar 2 n pasos en promedio antes de detenerse. Sólo necesita mantener un total acumulado del número de caras seguidas que ve, que puede contar en el espacio de registro.
Debido al teorema de Immerman-Szelepcsényi , según el cual NL es cerrado bajo complementos, el error unilateral en estos cálculos probabilísticos puede reemplazarse por un error de lado cero. Es decir, estos problemas pueden resolverse mediante máquinas probabilísticas de Turing que utilizan espacio logarítmico y nunca cometen errores. La clase de complejidad correspondiente que también requiere que la máquina use solo tiempo polinomial se llama ZPLP.
Así, cuando sólo miramos el espacio, parece que la aleatorización y el no determinismo son igualmente poderosos.
NL puede caracterizarse de manera equivalente mediante certificados , de forma análoga a clases como NP . Considere una máquina de Turing determinista limitada por un espacio logarítmico que tiene una cinta de entrada adicional de solo lectura y lectura única. Un idioma está en NL si y sólo si dicha máquina de Turing acepta cualquier palabra en el idioma para una elección adecuada de certificado en su cinta de entrada adicional, y rechaza cualquier palabra que no esté en el idioma, independientemente del certificado. [1]
Cem Say y Abuzer Yakaryılmaz han demostrado que la máquina de Turing de espacio logarítmico determinista de la afirmación anterior puede ser reemplazada por una máquina de Turing de espacio constante probabilística de error acotado a la que se le permite usar solo un número constante de bits aleatorios. [2]
Existe una caracterización lógica simple de NL : contiene precisamente aquellos lenguajes expresables en lógica de primer orden con un operador de cierre transitivo agregado .
La clase NL está cerrada bajo las operaciones complementación, unión y por tanto intersección, concatenación y estrella de Kleene .
