En la teoría de la complejidad computacional , una reducción del espacio logarítmico es una reducción calculable por una máquina de Turing determinista que utiliza el 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 tal máquina 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 de registro. Formalmente, esta reducción se ejecuta a través de un transductor de espacio logarítmico .
Una máquina de este tipo tiene configuraciones polinomialmente múltiples, por lo que las reducciones de espacio logarítmico también son reducciones de tiempo polinómico . 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, no completo en P es reducible en tiempo polinómico a cualquier otro lenguaje no vacío, no completo en P, una reducción del espacio logarítmico de un lenguaje NL -completo a un lenguaje en L , ambos de que serían lenguajes en P, implicarían lo poco probable L = NL. Es una pregunta abierta si los problemas NP-completos son diferentes con respecto a las reducciones de espacio logarítmico y tiempo polinómico.
Las reducciones de espacio logarítmico se usan 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 requerida ] , lo que significa que las reducciones de Turing se pueden usar para mostrar que un problema está en cualquiera de estas clases. Sin embargo, es posible que otras subclases de P, como NC , no se cierren con las reducciones de Turing, por lo que deben usarse reducciones de muchos uno [ cita requerida ] .
Así como las reducciones de tiempo polinómico son inútiles dentro de P y sus subclases, las reducciones de espacio logarítmico son inútiles para distinguir problemas en L y sus subclases; en particular, cada problema no vacío, no lleno en L es trivialmente L completo bajo reducciones de espacio logarítmico. Si bien existen reducciones aún más débiles, no se usan a menudo en la práctica, porque las clases de complejidad más pequeñas 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 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 utilizar como subrutinas en reducciones de espacio de registro.