L (complejidad)

En la teoría de la complejidad computacional , L (también conocida como LSPACE , LOGSPACE o DLOGSPACE ) es la clase de complejidad que contiene problemas de decisión que pueden ser resueltos por una máquina de Turing determinista utilizando una cantidad logarítmica de espacio de memoria escribible . ^{[1] [2]} Formalmente, la máquina de Turing tiene dos cintas, una de las cuales codifica la entrada y solo puede leerse, ^[3] mientras que la otra cinta tiene un tamaño logarítmico pero puede leerse y escribirse. El espacio logarítmico es suficiente para contener un número constante de punteros a 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 es completo bajo reducciones del espacio logarítmico , ^[4] por lo que se requieren reducciones más débiles para identificar nociones significativas de L -completitud, 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 demuestra 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 de teoría de grafos , esto convierte cada componente conectado en una clique ). Este resultado tiene aplicación a los lenguajes de consulta de bases de datos : la complejidad de datos de una consulta se define como la complejidad de responder a una consulta fija considerando el tamaño de los datos como la entrada variable. Para esta medida, las consultas contra bases de datos relacionales con información completa (sin noción de nulos ) como se expresa por ejemplo en el álgebra relacional están en L .

L es una subclase de NL , que es la clase de lenguajes decidibles en el espacio logarítmico en una máquina de Turing no determinista . Un problema en NL puede transformarse en un problema de alcanzabilidad en un grafo dirigido que representa estados y transiciones de estado de la máquina no determinista, y el límite del espacio logarítmico implica que este grafo tiene un número polinomial de vértices y aristas, de lo que se deduce que NL está contenido en la clase de complejidad P de problemas resolubles en tiempo polinomial determinista. ^[6] Por lo tanto , L  ⊆  NL  ⊆  P. La inclusión de L en P también se puede demostrar de forma más directa: un decisor que utiliza el espacio O (log  n ) no puede utilizar más de 2 ^{O (log  n )}  =  n ^{O (1)} tiempo, porque este es el número total de configuraciones posibles.

L se relaciona además con la clase NC de la siguiente manera: NC ¹  ⊆  L  ⊆  NL  ⊆  NC ² . En palabras, dada una computadora paralela C con un número polinomial O ( n ^k ) de procesadores para alguna constante k , cualquier problema que pueda resolverse en C en tiempo O (log  n ) está en L , y cualquier problema en L puede resolverse en tiempo O (log ²  n ) en C .

Problema sin resolver en informática :

⁠ ⁠${\displaystyle {\mathsf {L}}{\overset {?}{=}}{\mathsf {P}}}$

(más problemas sin resolver en informática)

Entre los problemas abiertos importantes se incluyen si L  =  P , ^[2] y si L  =  NL . ^[7] Ni siquiera se sabe si L  =  NP . ^[8]

La clase relacionada de problemas de función es FL . FL se utiliza a menudo para definir reducciones del espacio logarítmico .

L es bajo por sí mismo, porque puede simular consultas de oráculo en espacio de registro (en términos generales, "llamadas de función que utilizan espacio de registro") en espacio de registro, reutilizando el mismo espacio para cada consulta.

La idea principal del espacio logarítmico es que uno puede almacenar un número de magnitud polinomial en el espacio logarítmico y usarlo para recordar punteros a una posición de la entrada.

Por lo tanto, la clase logspace es útil para modelar cálculos en los que la entrada es demasiado grande para caber en la RAM de una computadora. Las secuencias de ADN y bases de datos largas son buenos ejemplos de problemas en los que solo una parte constante de la entrada estará en la RAM en un momento dado y donde tenemos punteros para calcular la siguiente parte de la entrada a inspeccionar, utilizando así solo memoria logarítmica.

• L/poly , una variante no uniforme de L que captura la complejidad de los programas de ramificación de tamaño polinomial

• Arora, Sanjeev; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4.Zbl 1193.68112  .
• Papadimitriou, Christos (1993). Computational Complexity (1.ª ed.). Addison Wesley. Capítulo 16: Espacio logarítmico, págs. 395–408. ISBN 0-201-53082-1.
• Sipser, Michael (1997). Introducción a la teoría de la computación . PWS Publishing. Sección 8.4: Las clases L y NL, págs. 294-296. ISBN 0-534-94728-X.
• Garey, MR ; Johnson, DS (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman. Sección 7.5: Espacio logarítmico, págs. 177-181. ISBN 0-7167-1045-5. Sr.  0519066. OCLC  247570676.
• Cook, Stephen A. ; McKenzie, Pierre (1987). "Problemas completos para el espacio logarítmico determinista" (PDF) . Revista de algoritmos . 8 (3): 385–394. doi :10.1016/0196-6774(87)90018-6. ISSN  0196-6774.