NL (complejidad)

Problema no resuelto en informática :

${\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}$

(más problemas sin resolver en informática)

En la teoría de la complejidad computacional , NL ( N ondeterministic L ogarithmic-space) es la clase de complejidad que contiene problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista usando una cantidad logarítmica de espacio de memoria .

NL es una generalización de L , la clase para problemas de espacio de registro 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á 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, informándonos 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 NL aún están abiertas (consulte Problemas sin resolver en informática ).

Ocasionalmente, NL se denomina RL debido a su definición probabilística a continuación; sin embargo, este nombre se usa con más frecuencia para referirse al espacio logarítmico aleatorio , que no se sabe que sea igual a NL .

Problemas de NL-complete

Se sabe que varios problemas son NL-completo bajo reducciones de espacio logarítmico , incluida la conectividad ST y la satisfacibilidad 2 . ST-conectividad pide nodos S y T en un gráfico dirigido si T es accesible a partir de S . 2-satisfacebilidad pregunta, dada una fórmula 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. Una instancia de ejemplo, donde indica que no , podría ser:${\displaystyle \neg }$

${\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}$

Contenciones

Se sabe que NL está contenido en P , ya que existe un algoritmo de tiempo polinomial 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 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 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:

${\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}$.

Más precisamente, NL está contenido en AC ¹ . 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 polinómico 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 como mucho más espacio cuadráticamente. Del teorema de Savitch, tenemos directamente que:

${\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalently, }}{\mathsf {NL\subseteq L}}^{2}.}$

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 deterministas y no deterministas son iguales, de modo que, por ejemplo, tenemos PSPACE = NPSPACE .

Definiciones alternativas

Definición probabilística

Supongamos que C es la clase de complejidad de problemas de decisión que se pueden resolver en el 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 polinomial, porque aunque tiene un número polinomial de configuraciones, puede usar la aleatoriedad para escapar de un bucle infinito. Si lo limitamos al tiempo polinomial, obtenemos la clase RL , que está contenida en, pero no se sabe ni se cree que sea igual a NL .

Existe un algoritmo simple que establece que C = NL . Claramente, C está contenido en NL , ya que:

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

Para mostrar que NL está contenido en C , simplemente tomamos un algoritmo NL y elegimos una ruta de cálculo aleatoria de longitud n , y hacemos esto 2 ⁿ veces. Debido a que ninguna ruta de cálculo excede la longitud n , y debido a que hay 2 ⁿ rutas de cálculo en total, tenemos una buena probabilidad de acertar con la de aceptación (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 sube a 2 ⁿ . Para evitar 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 ⁻ⁿ , esperamos dar 2 ⁿ pasos en promedio antes de detenerse. Solo necesita mantener un total acumulado de la cantidad de cabezas seguidas que ve, que puede contar en el espacio de registro.

Debido al teorema de Immerman-Szelepcsényi , según el cual NL se cierra bajo complementos, el error unilateral en estos cálculos probabilísticos puede reemplazarse por un error cero. Es decir, estos problemas pueden resolverse mediante máquinas probabilísticas de Turing que utilizan 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 .

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

Definición de certificado

NL se puede caracterizar de manera equivalente por certificados , análogos a clases como NP . Considere una máquina de Turing delimitada por espacios logarítmicos determinista que tiene una cinta de entrada adicional de solo lectura de una sola vez. Un idioma está en NL si y solo 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 en el enunciado anterior puede ser reemplazada por una máquina de Turing probabilística de espacio constante de error acotado a la que se le permite usar solo un número constante de bits aleatorios. ^[2]

Complejidad descriptiva

Hay 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 .

Propiedades de cierre

La clase NL se cierra bajo las operaciones de complementación, unión y, por tanto, intersección, concatenación y estrella de Kleene.

Notas

1. Arora, Sanjeev; Barak, Boaz (2009). "Definición 4.19". Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.
2. AC Cem Say, Abuzer Yakaryılmaz, "Verificadores de estados finitos con aleatoriedad constante", Métodos lógicos en informática , vol. 10 (3: 6) 2014, págs. 1-17.

Referencias

• Complejidad Zoo : NL
• Papadimitriou, C. (1994). "Capítulo 16: Espacio logarítmico". Complejidad computacional . Addison-Wesley. ISBN 0-201-53082-1.
• Michael Sipser (27 de junio de 1997). "Secciones 8.4–8.6: Las clases L y NL, NL-completitud, NL es igual a coNL". Introducción a la Teoría de la Computación . Publicación de PWS. págs.  294-302 . ISBN 0-534-94728-X.
• Introducción a la teoría de la complejidad: lección 7 . Oded Goldreich. Proposición 6.1. Nuestro C es lo que Goldreich llama badRSPACE (log n).