# 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. Espaço logarítmico é suficiente para manter um número constante de apontadores para entrada e um número logarítmico de flags booleanas, e muitos algoritmos básicos logspace utilizam a memória dessa forma.

## Problemas Completos e Caracterização Lógica

Todo problema não trivial em L é completo sob redução log-space, 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.
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.

## Classes de Complexidade Relacionadas

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. 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(logn)}$ = 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, e se L = NL.
A classe relacionada a problemas de função é FL. FL é frequentemente usado para definir reduções logspace.

## Propriedades Adicionais

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.

## Outros Usos

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.