NL-completo

Em teoria da complexidade computacional, NL-completo é uma classe de complexidade contendo as linguagens que são completas para NL, a classe de problemas de decisão que podem ser resolvidos por uma Máquina de Turing não determinística usando espaço de memória logarítmico. As linguagens NL-completas são os problemas mais “difíceis” ou “expressivos” em NL. Se existir um método de resolver qualquer um dos problemas NL-completos em espaço de memória logarítmico, então NL = L.

Definições

NL consiste em problemas de decisão que podem ser resolvidos por uma Máquina de Turing não determinística com uma fita de entrada somente-leitura e uma fita separada de somente-escrita cujo tamanho é proporcional ao logaritmo do tamanho da entrada. Similarmente, L consiste de linguagens que podem ser resolvidas por uma Máquina de Turing determinística com mesmo tamanho de fita. Por existir apenas um número polinomial de configurações distintas destas máquinas, ambos L e NL são subconjuntos da classe P dos problemas de decisão determinísticos de tempo polinomial.

Formalmente, um problema de decisão é NL-Completo quando ele pertence a NL, e tem a propriedade adicional que todo problema de decisão em NL pode ser reduzido a ele em espaço logarítmico. A menos que seja especificado, as reduções nesta definição precisam ser sobrejetivas a partir de um algoritmo determinístico de espaço logarítmico.

Propriedades

Se uma linguagem NL-Completa X pertencesse a L, então qualquer outra linguagem Y estaria em NL. Então, suponha (por NL-Completude) que existe uma redução determinística logespaço r que mapeia uma instância y do problema Y para uma instância x do problema X, e também (assumindo que x está em L) que existe um algoritmo determinístico A logespaço que resolve o problema X. Com estas suposições, um problema y na linguagem Y poderia ser resolvido em espaço logarítmico por uma algoritmo que simula o comportamento do algoritmo A com entrada r(y), usando o algoritmo de redução para simular cada acesso à fita de somente-leitura por r(y).

Isto se segue do teorema Immerman–Szelepcsényi que, se uma linguagem é co-NL-completa (isto é, se seu complemento é NL-completo) então a linguagem também é NL-completa ela própria.

Exemplos

Um problema importante NL-completo é o problema da Conectividade ST (ou "alcançabilidade") (Papadimitriou 1994 Teor. 16.2), o problema de se determinar se, dado um grafo G direcionado e dois nós s e t no grafo, existe um caminho de s para t. O problema da Conectividade ST pode ser visto como NL, pois inicia-se do nó s e não deterministicamente percorre-se qualquer outro nó alcançável. Conectividade ST é visto como NL-difícil por considerar o estado de computação do grafo de qualquer outro algoritmo NL e que o outro algoritmo irá aceitar se somente se é um caminho (não determinístico) do estado inicial para um estado de aceitação.

Outro problema importante NL-completo é o 2-Satisfatibilidade (2SAT, Papadimitriou 1994 Thrm. 16.3), o problema de se determinar se uma fórmula booleana na forma normal conjuntiva com dois literais por cláusula é satisfatível.

O problema da decifrabilidade de um dado código de comprimento variável foi demonstrado ser co-NL-completo por Rytter (1986); Rytter usou uma variante do algoritmo Sardinas–Patterson para mostrar que o problema complementar, encontrar uma cadeia que possui múltiplas codificações ambíguas, pertence a NL. Graças ao teorema de Immerman–Szelepcsényi, sabe-se que decifrabilidade única também é NL-completo.

Referências

• Papadimitriou, Christos H. (1994). Computational Complexity, Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.
• Rytter, Wojciech (1986), «The space complexity of the unique decipherability problem», Information Processing Letters, 23 (1): 1–3, MR 853618, doi:10.1016/0020-0190(86)90121-3 .