NL (complejidad)

NL es la clase de complejidad de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista (NTM) utilizando una cantidad logarítmica de espacio de memoria.

En más detalle, un idioma${\displaystyle L}$es NL si y solo si existe un NTM${\displaystyle M}$de tal manera que

• ${\displaystyle M}$Se ejecuta en el espacio de registro.
• ${\displaystyle M}$Siempre se detiene.

• Si${\displaystyle x\in L}$, entonces existe al menos un rastro computacional de${\displaystyle M(x)}$Esto provoca que la máquina se detenga en un estado de aceptación.
• Si${\displaystyle x\not \in L}$, entonces todos los rastros computacionales de${\displaystyle M(x)}$Esto provoca que la máquina se detenga en un estado de rechazo.

Supongamos que C es la clase de complejidad de problemas de decisión resolubles en espacio logarítmico con máquinas de Turing probabilísticas que nunca aceptan incorrectamente, pero a las que se les permite 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á limitado a tiempo polinomial, porque aunque tiene un número polinomial de configuraciones, puede usar la aleatoriedad para escapar de un bucle infinito. Si lo limitamos a 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 . Claramente, C está contenido en NL , ya que:

• Si la cadena no pertenece al idioma, ambas la rechazan en todas las rutas de cálculo.
• Si la cadena está en el lenguaje, un algoritmo NL la acepta a lo largo de al menos una ruta de cálculo y un algoritmo C la acepta a lo largo de al menos dos tercios de sus rutas de cálculo.

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 la ejecutamos 2n ^veces . Dado que ninguna ruta de cálculo excede la longitud n , y que hay 2n ^rutas de cálculo en total, tenemos una buena probabilidad de encontrar la ruta de aceptación (limitada inferiormente por una constante).

El único problema es que no tenemos espacio en el espacio logarítmico para un contador binario que llegue hasta 2ⁿ ^. Para solucionar esto, lo reemplazamos con un contador aleatorio , que simplemente lanza n monedas y se detiene y descarta si todas caen cara. Dado que este evento tiene una probabilidad de 2 ^{− n} , esperamos que tome 2ⁿ ^pasos en promedio antes de detenerse. Solo necesita mantener un total acumulado del número de caras consecutivas que ve, que puede contar en el espacio logarítmico.

Gracias 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 sustituirse por un error nulo. Es decir, estos problemas pueden resolverse mediante máquinas de Turing probabilísticas que utilizan espacio logarítmico y nunca cometen errores. La clase de complejidad correspondiente, que además requiere que la máquina utilice únicamente tiempo polinomial, se denomina ZPLP .

Por lo tanto, si solo consideramos el espacio, parece que la aleatorización y el no determinismo son igualmente poderosos.

NL puede caracterizarse de forma equivalente mediante certificados , análogos a clases como NP . Sea un verificador una máquina de Turing determinista con espacio logarítmico limitado que tiene una cinta de entrada adicional de solo lectura (es decir, el verificador solo puede mover el cabezal de lectura hacia adelante, nunca hacia atrás).

Un idioma${\displaystyle L}$está en NL si y solo si ^{[ 1 ] : Definición 4.19}

• Existe una función polinómica${\displaystyle p}$.
• Existe un verificador${\displaystyle TM}$.
• Para cualquier${\displaystyle x}$,${\displaystyle x\in L}$Si existe un certificado${\displaystyle u}$con longitud${\displaystyle |u|\leq p(|x|)}$, de tal manera que${\displaystyle TM(x,u)=1}$.

En otras palabras, significa que si una oración pertenece al lenguaje, entonces existe una prueba de longitud polinómica de que pertenece al lenguaje. No dice nada sobre el caso en que la oración no pertenece al lenguaje, aunque por el teorema de Immerman-Szelepcsényi, es claro que existe algún verificador que puede verificar ambas cosas.${\displaystyle x\in L}$y${\displaystyle x\not \in L}$.

Nótese que la condición de lectura única es necesaria. Si el verificador puede leer hacia adelante y hacia atrás, esto extiende la clase a la clase NP . ^{[ 1 ] : Ejercicio 4.7}

Cem Say y Abuzer Yakaryılmaz han demostrado que la máquina de Turing determinista en el espacio logarítmico del enunciado anterior puede ser reemplazada por una máquina de Turing probabilística de error limitado en el espacio constante que solo puede usar un número constante de bits aleatorios. ^{[ 2 ]}

En la teoría de la complejidad descriptiva , NL se define como aquellos lenguajes expresables en lógica de primer orden con un operador de cierre transitivo añadido.