En la teoría de la complejidad computacional , NL ( espacio logártimico 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 de Turing determinista . Dado que cualquier máquina de Turing determinista es también una máquina de Turing no determinista , tenemos que L está contenida 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 teoría de la complejidad nos permiten relacionar esta clase de complejidad con otras clases, lo que nos dice 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 preguntas importantes sobre NL aún están abiertas (ver Problemas sin resolver 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 , incluyendo la conectividad ST y la 2-satisfacibilidad . La conectividad ST pregunta, para los nodos S y T en un grafo dirigido , si T es alcanzable desde S. La 2-satisfacibilidad pregunta, dada una fórmula proposicional de la cual cada cláusula es la disyunción de dos literales, si hay una asignación de variable que hace que la fórmula sea verdadera. Un ejemplo, donde indica no , podría ser:
Se sabe que NL está contenido en P , ya que existe un algoritmo de tiempo polinomial para 2-satisfacibilidad , pero no se sabe si NL = P o si L = NL . Se sabe que NL = co-NL , donde co-NL es la clase de lenguajes cuyos complementos están en NL . Este resultado (el teorema de Immerman–Szelepcsényi ) fue descubierto independientemente por Neil Immerman y Róbert Szelepcsényi en 1987; recibieron el Premio Gödel en 1995 por este trabajo.
En cuanto a la complejidad de los circuitos , la NL puede ubicarse 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 solucionables 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 utilizando el teorema de Savitch , que nos dice que cualquier algoritmo no determinista puede ser simulado por una máquina determinista en un espacio como máximo cuadráticamente mayor. Del teorema de Savitch, tenemos directamente que:
Esta fue la inclusión más fuerte en el espacio determinista conocida en 1994 (Papadimitriou 1994, Problema 16.4.10, "Espacio simétrico"). Dado que las clases de espacio más grandes no se ven afectadas por incrementos 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 los problemas de decisión que se pueden resolver en el espacio logarítmico con máquinas de Turing probabilísticas que nunca aceptan incorrectamente, pero que pueden rechazar incorrectamente menos de 1/3 de las veces; esto se denomina error unilateral . La constante 1/3 es arbitraria; cualquier x con 0 ≤ x < 1/2 sería suficiente.
Resulta que C = NL . Nótese que C , a diferencia de su contraparte determinista L , no está limitada al tiempo polinomial, porque aunque tiene un número polinomial de configuraciones puede usar la aleatoriedad para escapar de un bucle infinito. Si la limitamos al tiempo polinomial, obtenemos la clase RL , que está contenida en NL , pero no se sabe ni se cree que sea igual a ella .
Existe un algoritmo sencillo que establece que C = NL . Es evidente que C está contenido en NL , ya que:
Para demostrar que NL está contenido en C , simplemente tomamos un algoritmo NL y elegimos una ruta de cálculo aleatoria de longitud n , y lo ejecutamos 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 probabilidad de encontrar la que lo acepte (limitada por debajo por una constante).
El único problema es que no tenemos espacio en el espacio logarítmico para un contador binario que llegue hasta 2 n . Para solucionarlo, lo reemplazamos con un contador aleatorio , que simplemente lanza n monedas y se detiene y rechaza si todas caen en cara. Como este evento tiene una probabilidad de 2 − n , esperamos dar 2 n pasos en promedio antes de detenerse. Solo necesita mantener un total acumulado de la cantidad de caras seguidas que ve, que puede contar en el espacio logarítmico.
Debido al teorema de Immerman-Szelepcsényi , según el cual la NL es cerrada bajo complementos, el error unilateral en estos cálculos probabilísticos puede ser reemplazado por un error unilateral. Es decir, estos problemas pueden ser resueltos por máquinas de Turing probabilísticas que usan el 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.
El lenguaje no lineal puede ser caracterizado de manera equivalente por certificados , de manera análoga a clases como NP . Consideremos 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 lenguaje está en lenguaje no lineal si y solo si dicha máquina de Turing acepta cualquier palabra del lenguaje para una elección apropiada de certificado en su cinta de entrada adicional, y rechaza cualquier palabra que no esté en el lenguaje independientemente del certificado. [1]
Cem Say y Abuzer Yakaryılmaz han demostrado que la máquina de Turing determinista de espacio logarítmico en 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]
Hay una caracterización lógica simple del 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 lo tanto, intersección, concatenación y estrella de Kleene .
