Redução em espaço logarítmico

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde julho de 2012).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Question book.svg
Esta página ou se(c)ção não cita fontes fiáveis e independentes (desde julho de 2012). Por favor, adicione referências e insira-as no texto ou no rodapé, conforme o livro de estilo. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros, acadêmico)Yahoo!Bing.
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde julho de 2012).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.

Na Teoria da Computação, uma redução em espaço logaritmico, é uma redução computável por uma maquina de Turing deterministica usando espaço logarítmico. Conceitualmente, isso significa que ela pode manter uma número constante de ponteiros para a entrada, junto com um número logaritmico de inteiros de tamanho fixo. Já que tal máquina possui uma quantidade polinomial de configurações possíveis, reduções de espaço logaritmico são também reduções de tempo polinomiais.[1]

Características[editar | editar código-fonte]

Reduções de espaço logaritmico são provavelmente mais fracas que reduções de tempo polinomial; enquanto qualquer linguágem não vazia, não cheia em P é redutível em tempo polinomial a qualquer linguágem, não vazia, não cheia em P, a redução em espaço polinomial entre uma linguágem em NL e uma linguágem em L, ambas sendo subconjuntos de P, significaria o improvável L = NL. É uma questão ainda em aberto se os problemas NP-Completos são diferentes com respeito a reduções em espaço logaritmico e a tempo polinomial.

Reduções de espaço logaritmico são utilizadas normalmente e linguágens em P, onde normalmente não é importante se redução por mapeamento ou Turing reduções são usadas, já que já foi verificado que L, SL, NL, e P são todos fechados sob Turing reduções, significando que Turing reduções podem ser utilizadas para mostrar que um problema está em qualquer uma dessas classes. Porém, outras subclasses de P como NC podem não ser fechadas sob Turing reduções, e por isso uma redução por mapeamento deve ser utilizada.

Notoriedade[editar | editar código-fonte]

Assim como reduções de tempo polinomial são inúteis para P e suas subclasses, reduções de espaço logarítmico são inúteis para distinguir problemas em L e suas subclasses; em particular, quase todos os problemas em L são trivialmente L-completos sob redução de espaço logarítmico. Ainda que reduções mais fracas existam, elas não são comumente utilizadas na prática, porque classes de complexidade menores que L (ou seja, estritamente ou supostamente contidas em L) recebem relativamente pouca atenção.

A prova do teorema "L = SL" forneceu novas ferramentas para pesquisadores que trabalham com redução em espaço logarítmico.

Ver também[editar | editar código-fonte]

Referências

  1. Christos Papadimitriou. Computational Complexity. 1st edition ed. [S.l.]: Addison Wesley, 1994. 159–180 pp. ISBN 0-201-53082-1