En la teoría de la complejidad computacional , L (también conocida como LSPACE o DLOGSPACE ) es la clase de complejidad que contiene problemas de decisión que pueden resolverse mediante una máquina de Turing determinista utilizando una cantidad logarítmica de espacio de memoria grabable . [1] [2] Formalmente, la máquina de Turing tiene dos cintas, una de las cuales codifica la entrada y solo se puede leer, [3] mientras que la otra cinta tiene un tamaño logarítmico pero se puede leer y escribir. El espacio logarítmico es suficiente para contener un número constante de punteros en la entrada [1] y un número logarítmico de indicadores booleanos, y muchos algoritmos básicos de espacio logarítmico utilizan la memoria de esta manera.
Todo problema no trivial en L está completo bajo reducciones en el espacio logarítmico , [4] por lo que se requieren reducciones más débiles para identificar nociones significativas de completitud en L , siendo las más comunes las reducciones de primer orden .
Un resultado de 2004 de Omer Reingold muestra que USTCON , el problema de si existe un camino entre dos vértices en un gráfico no dirigido dado , está en L , lo que muestra que L = SL , ya que USTCON es SL -completo. [5]
Una consecuencia de esto es una caracterización lógica simple de L : contiene precisamente aquellos lenguajes expresables en lógica de primer orden con un operador de cierre transitivo conmutativo agregado (en términos teóricos de grafos , esto convierte cada componente conectado en una camarilla ). Este resultado tiene aplicación a los lenguajes de consulta de bases de datos : la complejidad de los datos de una consulta se define como la complejidad de responder una consulta fija considerando el tamaño de los datos como entrada variable. Para esta medida, las consultas a bases de datos relacionales con información completa (sin noción de nulos ) como se expresa, por ejemplo, en álgebra relacional están en L.
L es una subclase de NL , que es la clase de lenguajes decidibles en espacio logarítmico en una máquina de Turing no determinista . Un problema en NL puede transformarse en un problema de alcanzabilidad en un gráfico dirigido que representa estados y transiciones de estado de la máquina no determinista, y el límite espacial logarítmico implica que este gráfico tiene un número polinómico de vértices y aristas, de lo que se deduce que NL está contenido en la clase de complejidad P de problemas solucionables en tiempo polinomial determinista. [6] Por lo tanto L ⊆ NL ⊆ P . La inclusión de L en P también se puede demostrar de manera más directa: un decisor que usa el espacio O (log n ) no puede usar más de 2 O (log n ) = n O (1) tiempo, porque este es el número total de configuraciones posibles.
L además se relaciona con la clase NC de la siguiente manera: NC 1 ⊆ L ⊆ NL ⊆ NC 2 . En palabras, dada una computadora paralela C con un número polinómico O ( n k ) de procesadores para alguna constante k , cualquier problema que pueda resolverse en C en O (log n ) tiempo está en L , y cualquier problema en L puede ser resuelto en tiempo O (log 2 n ) en C .
Los problemas abiertos importantes incluyen si L = P , [2] y si L = NL . [7] Ni siquiera se sabe si L = NP . [8]
La clase relacionada de problemas de funciones es FL . FL se utiliza a menudo para definir reducciones de espacio logarítmico .
L es bajo en sí mismo, porque puede simular consultas de Oracle en el espacio de registro (en términos generales, "llamadas a funciones que usan espacio de registro") en el espacio de registro, reutilizando el mismo espacio para cada consulta.
La idea principal del espacio de registro es que se puede almacenar un número de magnitud polinómica en el espacio de registro y usarlo para recordar punteros a una posición de la entrada.
Por lo tanto, la clase logspace es útil para modelar cálculos donde la entrada es demasiado grande para caber en la RAM de una computadora. Las secuencias largas de ADN y las bases de datos son buenos ejemplos de problemas en los que sólo una parte constante de la entrada estará en la RAM en un momento dado y en los que tenemos punteros para calcular la siguiente parte de la entrada a inspeccionar, utilizando así sólo memoria logarítmica.
