LSPACE

Em teoria da complexidade, L (também conhecido como LSPACE ou DLOGSPACE) é a classe de complexidade que contém problemas de decisão os quais podem ser resolvidos por uma máquina de Turing utilizando uma quantidade de espaço de memória logarítmico.^[1][2] Espaço logarítmico é suficiente para manter um número constante de apontadores para entrada^[1] e um número logarítmico de flags booleanas, e muitos algoritmos básicos logspace utilizam a memória dessa forma.

Todo problema não trivial em L é completo sob redução log-space,^[3] reduções mais fracas são necessárias para identificar noções significativas de L-completude, as reduções mais comuns são as reduções de primeira ordem.

Um resultado de 2004 por Omer Reingold mostra que USTCON, o problema de saber se existe um caminho entre dois vértices de um dado grafo não-dirigido, está em L, ele mostra que L = SL, uma vez que USTCON é SL-completo.^[4]

Uma consequência disto é uma caracterização lógica simples do L: ele contém precisamente essas línguas que são expressas em lógica de primeira ordem com o incremento de um operador de fecho transitivo e comutativo (em termos teóricos gráfico, isto transforma cada componente conectado em um clique). Este resultado tem aplicação para linguagens de consulta de banco de dados: a complexidade dos dados de uma consulta é definida como a complexidade da resposta a uma consulta fixa considerando o tamanho de dados como a entrada variável. Para esta medida, consultas em bancos de dados relacionais com informações completas (não tendo nenhuma noção de valores nulos) expressa, por exemplo, na álgebra relacional estão em L.

L é uma subclasse de NL. NL é a classe de linguagens decidíveis no espaço logarítmico em uma máquina de Turing não-determinística. Um problema em NL pode ser transformado em um problema de acessibilidade em um grafo direcionado representando estados e transições de estado da máquina não determinística, e o espaço logarítmico vinculado implica que este grafo tem um número polinomial de vértices e arestas, da qual resulta que a classe NL está contida na classe de complexidade P de problemas que podem ser resolvidos em tempo polinomial determinístico.^[5] Assim L ⊆ NL ⊆ P. A inclusão de L em P pode ser provado mais diretamente: um decisor usando espaço O(log n) não pode usar tempo maior que 2^O(log n) = n^O(1) vezes, porque este é o número total de configurações possíveis.

L refere-se ainda à classe NC da seguinte maneira: NC¹ ⊆ L ⊆ NL ⊆ NC².

Em outras palavras, dado um computador paralelo C com um número polinomial O(n^k) de processadores para alguma constante k, qualquer problema que pode ser resolvido de C em tempo O(log n) está em L, e qualquer problema em L pode ser resolvido em tempo O(log² n) de C.

Importantes problemas em aberto incluem se L = P,^[2] e se L = NL.^[6]

A classe relacionada a problemas de função é FL. FL é frequentemente usado para definir reduções logspace.

L tem complexidade low, porque ele pode simular consultas Oracle log-space (à grosso modo, "chamadas de função que usam log space") no espaço de log, reutilizando o mesmo espaço para cada consulta.

A ideia principal do logspace é que você pode armazenar um número de magnitude polinomial em logspace e usá-lo para lembrar ponteiros de uma posição da entrada.

A classe logspace é, portanto, útil para o modelo de computação onde a entrada é demasiadamente grande para caber na memória RAM de um computador. Sequências de DNA longas e bancos de dados são bons exemplos de problemas em que apenas uma parte da constante de entrada será na RAM em um determinado momento e onde temos ponteiros para calcular a próxima parte da entrada para inspecionar, assim, usando somente a memória logarítmica.

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. [S.l.]: Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112 
• Papadimitriou, Christos (1993). Computational Complexity 1st ed. [S.l.]: Addison Wesley. Chapter 16: Logarithmic space, pp. 395–408. ISBN 0-201-53082-1 
• Sipser, Michael (1997). Introduction to the Theory of Computation. [S.l.]: PWS Publishing. Section 8.4: The Classes L and NL, pp. 294–296. ISBN 0-534-94728-X 
• Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. [S.l.]: W.H. Freeman. Section 7.5: Logarithmic Space, pp. 177–181. ISBN 0-7167-1045-5