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.
Problemas Completos e Caracterização Lógica
[editar | editar código-fonte]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.
Classes de Complexidade Relacionadas
[editar | editar código-fonte]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 2O(log n) = nO(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(nk) 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.
Propriedades Adicionais
[editar | editar código-fonte]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
[editar | editar código-fonte]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.
Notas e referências
- ↑ a b Sipser (1997), Definition 8.12, p. 295.
- ↑ a b Garey & Johnson (1979), p. 177.
- ↑ See Garey & Johnson (1979), Theorem 7.13 (claim 2), p. 179.
- ↑ Reingold, Omer (2005). Undirected ST-connectivity in log-space. STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York. pp. 376–385. MR 2181639. doi:10.1145/1060590.1060647. Predefinição:ECCC
- ↑ Sipser (1997), Corollary 8.21, p. 299.
- ↑ Sipser (1997), p. 297; Garey & Johnson (1979), p. 180.
Bibliografia
[editar | editar código-fonte]- 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