LSPACE

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto.
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Na teoria da complexidade computacional, L (também conhecida como LSPACE) é a classe de complexidade que contém os problemas de decisão que podem ser solucionado por uma máquina de Turing determinística usando uma quantidade logarítmica de memória. O espaço logarítimico é suficiente para conter um número constante de ponteiros para a entrada e um número logarítmico de sinalizadores boleanos. Muitos algoritimos de espaço logarítimico utilizando a memória desta forma.

L é uma subclasse de NL, que é a classe das linguagens decidíveis em espaço logarítimico por uma máquina de Turing não-determinística. Usando a construção do teorema de savitch, pode-se ver que NL está contida na classe de complexidade P dos problemas solúveis em tempo polinomial determinísticamente. Logo, L ⊆ NL ⊆ P. A inclusão de L em P pode também ser provada mais diretamente: um decisor usando espaço O(log n) não pode usar mais tempo do que 2O(log n) = nO(1), por que este é o número total de configurações possíveis.

Todo problema não trivial em L é completo para redução logarítimica de espaço, logo reduções fracas são necessárias para identificar uma noção que faça sentido de completude em L. Tais reduções incluem reduções em NC e reduções em DLOGTIME.

Importantes problemas em aberto incluem se L = P, e se L = NL.

A classe de problemas de função é FL. FL é muitas vezes utilizado para definir reduções para espaço logarítimico.

Em 2004 um documento1 escrito por Omer Reingold mostrou que USTCON, o problema de se existe um caminho entre dois vertíces dado um grafo não direcionado, está em L, estabelecendo que L = SL, dado que USTCON é SL-completo.

Uma consequencia disto é uma simples caracterização lógica de L: esta contém precisamente as linguagens expressíveis em lógica de primeira ordem adicionadas de um operador de transitividade comunitativa (em termos da teoria dos grafos, isto torna todo componete conectado do grafo em um clique.

L é definida como complexidade baixa, pois pode simular em espaço logarítimico buscas no oracle (falando de maneira direta, "chamadas de funções que utilizam espaço logarítimico") em espaço logarítimico, reutilizando o mesmo espaço de memória para cada uma das buscas.

Fora do mundo da complexidade[editar | editar código-fonte]

A principal idéia de logspace é que você pode muitas vezes contar coisas de tamanho polinomial utilizando espaço logarítimico e guardar ponteiros para dada posição da entrada.

A classe logspace é útil para modelar computação onde a entrada é muito grande para memória disponível de um computador. Sequencias longas de DNA e banco de dados são bons exemplos de problemas onde apenas uma parte contante da entrada estará na memória em um dado momento onde teremos ponteiros para as próximas parte da entrada a serem inspecionadas, isto utilizando apenas memória logarítimica.

Referencias[editar | editar código-fonte]

  1. Undirected ST-connectivity in Log-Space. Omer Reingold. Electronic Colloquium on Computational Complexity. No. 94.