En la teoría de la complejidad computacional , una reducción en el espacio logarítmico es una reducción computable mediante una máquina de Turing determinista que utiliza un espacio logarítmico . Conceptualmente, esto significa que puede mantener un número constante de punteros en la entrada, junto con un número logarítmico de números enteros de tamaño fijo . [1] Es posible que una máquina de este tipo no tenga espacio para escribir su propia salida, por lo que el único requisito es que cualquier bit dado de la salida sea computable en el espacio logarítmico. Formalmente, esta reducción se ejecuta mediante un transductor de espacio logarítmico .
Una máquina de este tipo tiene muchas configuraciones polinómicas, por lo que las reducciones del espacio logarítmico también son reducciones del tiempo polinomial . Sin embargo, las reducciones de espacio logarítmico son probablemente más débiles que las reducciones de tiempo polinomial; mientras que cualquier lenguaje no vacío y no completo en P es reducible en tiempo polinomial a cualquier otro lenguaje no vacío y no completo en P, una reducción en espacio logarítmico de un lenguaje completo en NL a un lenguaje en L , ambos cuales serían idiomas en P, implicaría lo improbable L = NL. Es una cuestión abierta si los problemas NP-completos son diferentes con respecto a las reducciones de espacio logarítmico y de tiempo polinomial.
Las reducciones de espacio logarítmico se utilizan normalmente en lenguajes en P, en cuyo caso generalmente no importa si se usan reducciones de muchos uno o reducciones de Turing , ya que se ha verificado que L, SL , NL y P están todos cerrados bajo Turing. reducciones [ cita necesaria ] , lo que significa que las reducciones de Turing se pueden utilizar para mostrar que un problema está en cualquiera de estas clases. Sin embargo, otras subclases de P, como NC, no pueden cerrarse bajo las reducciones de Turing, por lo que se deben utilizar reducciones de muchos uno [ cita necesaria ] .
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 que se cree que están estrictamente contenidas en L) reciben relativamente poca atención.
Las herramientas disponibles para los diseñadores de reducciones de espacio logarítmico se han ampliado enormemente con el resultado de que L = SL; consulte SL para obtener una lista de algunos problemas completos de SL que ahora se pueden usar como subrutinas en reducciones de espacio de registro.