En la teoría de la complejidad computacional , una reducción en el espacio logarítmico es una reducción computable 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 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 a través de un transductor de espacio logarítmico .
Una máquina de este tipo tiene configuraciones polinómicas múltiples, por lo que las reducciones en el espacio logarítmico también son reducciones en tiempo polinómico . Sin embargo, las reducciones en el espacio logarítmico son probablemente más débiles que las reducciones en tiempo polinómico; mientras que cualquier lenguaje no vacío ni completo en P es reducible en tiempo polinómico a cualquier otro lenguaje no vacío ni completo en P, una reducción en el espacio logarítmico de un lenguaje NL -completo a un lenguaje en L , los cuales serían lenguajes en P, implicaría el improbable L = NL. Es una pregunta abierta si los problemas NP-completos son diferentes con respecto a las reducciones en el espacio logarítmico y en tiempo polinómico.
Las reducciones del espacio logarítmico se utilizan normalmente en lenguajes en P, en cuyo caso normalmente no importa si se utilizan reducciones de muchos-uno o reducciones de Turing , ya que se ha verificado que L, SL , NL y P están todos cerrados bajo reducciones de Turing [ cita requerida ] , 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 pueden no estar cerradas bajo reducciones de Turing, y por lo tanto se deben utilizar reducciones de muchos-uno [ cita requerida ] .
Así como las reducciones en tiempo polinomial son inútiles dentro de P y sus subclases, las reducciones en el 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 el espacio logarítmico. Si bien existen reducciones aún más débiles, no se las suele usar 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 en el espacio logarítmico se han ampliado enormemente con el resultado de que L = SL; consulte SL para obtener una lista de algunos problemas SL-completos que ahora se pueden usar como subrutinas en reducciones en el espacio logarítmico.