Redução em espaço logarítmico

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.

Características

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

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

• Complexidade Logarítmica
• Complexidade (informática)
• Complexidade NL
• LSPACE