L (complejidad) - L (complexity)
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 ser resueltos por una máquina de Turing determinista utilizando una cantidad logarítmica de espacio de memoria grabable . Formalmente, la máquina de Turing tiene dos cintas, una de las cuales codifica la entrada y solo se puede leer, 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 y un número logarítmico de indicadores booleanos, y muchos algoritmos de espacio logarítmico básicos utilizan la memoria de esta manera.
Problemas completos y caracterización lógica
Cada problema no trivial en L está completo bajo reducciones de espacio logarítmico , por lo que se requieren reducciones más débiles para identificar nociones significativas de L -completo, 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 una ruta entre dos vértices en un gráfico no dirigido dado , está en L , mostrando que L = SL , ya que USTCON es SL -completo.
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 gráficos , esto convierte a 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 a una consulta fija considerando el tamaño de los datos como entrada variable. Para esta medida, consultas en bases de datos relacionales con información completa (que no tiene noción de valores nulos ) tal como se expresa por ejemplo en álgebra relacional están en L .
Clases de complejidad relacionadas
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 accesibilidad en un grafo dirigido que representa estados y transiciones de estado de la máquina no determinista, y la cota del espacio logarítmico implica que este grafo tiene un número polinomial de vértices y aristas, de lo cual se sigue que NL está contenido en la clase de complejidad P de problemas que se pueden resolver en tiempo polinomial determinista. Por lo tanto L ⊆ NL ⊆ P . La inclusión de L en P también se puede probar más directamente: 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 polinomial 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 O (log 2 n ) el tiempo en C .
Los problemas abiertos importantes incluyen si L = P y si L = NL . Ni siquiera se sabe si L = NP .
La clase relacionada de problemas de función es FL . FL se utiliza a menudo para definir reducciones de espacio de registro .
Propiedades adicionales
L es baja por sí misma, 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.
Otros usos
La idea principal del espacio de registro es que se puede almacenar un número de magnitud polinomial en el espacio de registro y usarlo para recordar punteros a una posición de la entrada.
Por lo tanto, la clase de espacio de registro 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 largas y las bases de datos 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 para inspeccionar, por lo tanto, utilizando solo memoria logarítmica.
Ver también
- L / poly , una variante no uniforme de L que captura la complejidad de los programas de ramificación de tamaño polinomial
Notas
Referencias
- Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Prensa de la Universidad de Cambridge . ISBN 978-0-521-42426-4. Zbl 1193.68112 .
- Papadimitriou, Christos (1993). Complejidad computacional (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 . Publicación de PWS. 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 NP-Completeness . WH Freeman. Sección 7.5: Espacio logarítmico, págs. 177-181 . ISBN 0-7167-1045-5.
- 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 .