NL-completo: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 22h00min de 14 de julho de 2015

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 o 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 .

@@ Linha 1: / Linha 1: @@
-Em [[teoria da complexidade computacional]], '''NL-completo''' é uma [[classe de complexidade]] contendo as linguagens que são [[completa]]s sob '''[[Complexidade NL|NL]]''', a classe de [[Problema de decisão|problemas de decisão]] que pode ser resolvida por uma [[Máquina de Turing não determinística]] usando [[LSPACE|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'''.
+Em [[teoria da complexidade computacional]], '''NL-completo''' é uma [[classe de complexidade]] contendo as linguagens que são [[completa]]s para '''[[Complexidade NL|NL]]''', a classe de [[Problema de decisão|problemas de decisão]] que podem ser resolvidos por uma [[Máquina de Turing não determinística]] usando [[LSPACE|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 [[Problema de decisão|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 o 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 (complexidade)|P]] dos problemas de decisão determinísticos de tempo polinomial.
-Formalmente, um [[Problema de decisão|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 [[Redução (complexidade)|reduzido]] a ele. A menos que seja especificado, as reduções nesta definição precisam ser sobrejetivas a partir de um algoritmo determinístico de espaço logaritmo.
+Formalmente, um [[Problema de decisão|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 [[Redução (complexidade)|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 somente-leitura por ''r(y)''.
+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 [[Teorema de Immerman–Szelepcsényi|Immerman–Szelepcsényi]] que, se uma linguagem é co-NL-completa (isto é, se seu [[Complementar|complemento]] é NL-completo) então a linguagem também é NL-completa por si só.
+Isto se segue do teorema [[Teorema de Immerman–Szelepcsényi|Immerman–Szelepcsényi]] que, se uma linguagem é co-NL-completa (isto é, se seu [[Complementar|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|Conectividade ST]] (ou "alcançabilidade") (Papadimitriou 1994 Teor. 16.2), o problema de 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.
+Um problema importante NL-completo é o problema da [[Conectividade st|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 determinar se uma fórmula booleana na [[Forma normal conjuntiva|forma normal conjuntiva]] com duas variáveis por cláusula é satisfatível.
+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|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 {{harvtxt|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.