Reducción del espacio logarítmico

En la teoría de la complejidad computacional , una reducción en espacio logarítmico es una reducción computable por una máquina de Turing determinista que utiliza espacio logarítmico . Conceptualmente, esto significa que la máquina de Turing puede mantener un número constante de punteros a la entrada, junto con un número logarítmico de enteros de tamaño fijo . Es posible que dicha máquina no tenga espacio para escribir su propia salida, por lo que el único requisito es que cualquier bit de la salida sea computable en espacio logarítmico. Formalmente, esta reducción se ejecuta mediante un transductor en espacio logarítmico .

Una máquina de este tipo tiene un número polinomial de configuraciones, por lo que las reducciones en espacio logarítmico también son reducciones en tiempo polinomial . Sin embargo, las reducciones en espacio logarítmico son probablemente más débiles que las reducciones en tiempo polinomial; mientras que cualquier lenguaje no vacío ni completo en P es reducible en tiempo polinomial a cualquier otro lenguaje no vacío ni completo en P, una reducción en espacio logarítmico de un lenguaje NL -completo a un lenguaje en L , ambos lenguajes en P, implicaría la improbable L = NL. Queda por determinar si los problemas NP-completos difieren con respecto a las reducciones en espacio logarítmico y en tiempo polinomial.

Las reducciones en espacio logarítmico se utilizan normalmente en lenguajes de P, en cuyo caso no suele importar si se utilizan reducciones de muchos a uno o reducciones de Turing , puesto que se ha verificado que L, SL , NL y P son todos cerrados bajo reducciones de Turing en espacio logarítmico , lo que significa que las reducciones de Turing pueden utilizarse para demostrar que un problema pertenece a cualquiera de estas clases. Sin embargo, otras subclases de P, como NC, pueden no ser cerradas bajo reducciones de Turing, por lo que deben utilizarse reducciones de muchos a uno .

Así como las reducciones en tiempo polinomial son inútiles dentro de P y sus subclases, las reducciones en espacio logarítmico son inútiles para distinguir problemas en L y sus subclases; en particular, todo problema no vacío ni lleno en L es trivialmente L- completo bajo reducciones en espacio logarítmico. Si bien existen reducciones aún más débiles, no se utilizan con frecuencia en la práctica, porque las clases de complejidad menores que L (es decir, estrictamente contenidas o consideradas estrictamente contenidas en L) reciben relativamente poca atención.

Las herramientas disponibles para los diseñadores de reducciones en espacio logarítmico se han ampliado enormemente gracias al resultado de que L = SL; consulte SL para obtener una lista de algunos problemas SL-completos que ahora se pueden utilizar como subrutinas en reducciones en espacio logarítmico.

Una función${\displaystyle f:2^{*}\to 2^{*}}$es (implícitamente) computable en espacio logarítmico si: ^{[ 1 ] : 88}

• Su longitud de salida está acotada polinómicamente: existe algún${\displaystyle c>0}$de tal manera que${\displaystyle f(x)\leq |x|^{c}}$a pesar de${\displaystyle x\in 2^{*}}$.
• ${\displaystyle L_{f}=\left\{\langle x,i\rangle \mid f(x)_{i}=1\right\}}$pertenece a la clase de complejidad L.
• ${\displaystyle L_{f}^{\prime }=\{\langle x,i\rangle \mid i\leq |f(x)|\}}$pertenece a la clase de complejidad L.

Intuitivamente, la primera condición establece que la función debe generar salidas lo suficientemente cortas como para que la creación de un único puntero a la salida ocupe solo espacio logarítmico. Esta condición es necesaria para que existan punteros a la salida.

La segunda condición establece que cualquier ubicación de salida particular se puede calcular en el espacio de registros.

La tercera condición establece que la comprobación de si un puntero es un puntero válido es decidible en el espacio de registros.

De forma equivalente, una función${\displaystyle f:2^{*}\to 2^{*}}$es computable en espacio logarítmico si es computado por una máquina de Turing con una cinta de trabajo de longitud logarítmica, que se detiene en cualquier entrada, y una cinta de salida que es de solo escritura y escritura única, lo que significa que en cada paso, la máquina puede no escribir nada, o escribir un bit y mover el cabezal de escritura hacia adelante en uno. ^{[ 1 ] : 94} Dicha máquina se suele llamar transductor de espacio logarítmico . Nótese que dicha máquina, si se detiene, debe detenerse en pasos polinomiales, ya que su cinta de trabajo tiene longitud logarítmica. Por lo tanto, su longitud de salida está acotada polinomialmente.

Una intuición es que dicha función puede ser calculada por un programa que solo puede mantener un número constante de punteros a la entrada y un número constante de contadores que solo pueden contener enteros de tamaño${\displaystyle {\mathsf {poly}}(n)}$Esto se debe a que una máquina contadora con un número constante de contadores que cuentan hasta${\displaystyle f(n)}$es equivalente a una máquina de Turing con complejidad espacial${\displaystyle O(\log f(n))}$. ^{[ 2 ]}

Un idioma${\displaystyle L}$¿Es reducible el espacio de registros (muchos a uno) a otro lenguaje?${\displaystyle L'}$, anotado como${\displaystyle L\leq _{l}L'}$, si existe una función computable implícitamente en el espacio logarítmico${\displaystyle f}$de tal manera que${\displaystyle x\in L\iff f(x)\in L'}$Esta es una relación transitiva, porque la computabilidad del espacio logarítmico es cerrada bajo composición, como se demostró anteriormente.

Un idioma${\displaystyle L}$es NL-completo si está en NL y cualquier lenguaje en NL es reducible a él mediante espacio logarítmico.

La mayoría de las reducciones de tiempo polinomial que ocurren naturalmente en la teoría de la complejidad son reducciones de espacio logarítmico. En particular, esto es cierto para la demostración estándar que muestra que el problema SAT es NP-completo y que el problema de valor de circuito es P-completo . Este también suele ser el caso para demostrar que el verdadero problema de fórmula booleana cuantificada es PSPACE-completo . Esto se debe a que la necesidad de memoria en tales construcciones de reducción es para contar hasta${\displaystyle p(n)}$para algún polinomio${\displaystyle p}$en la longitud de entrada${\displaystyle n}$y esto se puede hacer en el espacio logarítmico. ^{[ 3 ] : 180}

Si bien la reducción logspace de muchos a uno implica una reducción polinomial de muchos a uno, se desconoce si esto constituye una equivalencia, o si existen problemas que son NP-completos bajo la reducción polinomial, pero no bajo la reducción logspace. Cualquier solución a este problema resolvería el siguiente problema: ¿Son los autómatas lineales acotados deterministas equivalentes a los autómatas lineales acotados no deterministas? ^{[ 4 ]}

• Papadimitriou, Christos (1994). «Capítulo 8: Reducciones y completitud». Complejidad computacional (1.ª  ed.). Addison Wesley. pp. 159–180 . ISBN  0-201-53082-1. Zbl 0833.68049 . 
• Szepietowski, Andrzej (1994). Máquinas de Turing con espacio sublogarítmico . Springer Press. ISBN 3-540-58355-6.
• Sipser, Michael (2012). Introducción a la teoría de la computación . Cengage Learning. ISBN 978-0-619-21764-8.