Complexidade NL

Na teoria da complexidade, NL (espaço-logarítmico não-determinístico) é a classe de complexidade contendo problemas de decisão que podem ser resolvidos por uma máquina de Turing não-determinística, usando uma quantidade de espaço de memória logarítmica.

NL é uma generalização de L, a classe dos problemas de espaço logarítmico em uma máquina de Turing determinística. Desde que qualquer máquina de Turing seja também uma máquina de Turing não-determinística, nós temos que L está contida em NL.

NL pode ser formalmente definida em termos de recursos computacionais de espaço não-determinístico (ou NSPACE) como NL = NSPACE(log n).

Importantes resultados em teoria da complexidade nos permitem relacionar esta classe de complexidade com outras classes, dizendo-nos algo sobre o poder relativo dos recursos envolvidos. Resultados na área de algoritmos, por outro lado, nos informam quais problemas podem ser resolvidos com este recurso. Infelizmente, como grande parte da teoria da complexidade, muitas questões importantes sobre NL ainda estão abertas.

Ocasionalmente, NL é referida como RL devido a sua definição probabilística abaixo. No entanto, esse nome é mais frequentemente usado para referir espaços logarítmicos aleatórios, o qual não é conhecido como sendo NL.

Problemas NL completos

O "mais difícil" ou "mais expressivo" problema na classe de complexidade são problemas que são completos para aquela classe. Intuitivamente, se tivermos um método para resolver um problema completo com poucos recursos, nós podemos usar isso para resolver qualquer outro problema nesta classe com poucos recursos. Estes problemas caracterizam o poder e a expressividade da classe de complexidade.

Vários problemas são conhecidos por serem NL-completos sob reduções espaço-logarítmicas, incluindo conectividade-ST e 2-satisfatibilidade. Conectividade-ST pede por vértices S e T em um grafo direcionado se T é acessível a partir de S. E 2-satisfabilidade pergunta, dada uma fórmula em que cada cláusula é uma disjunção de dois literais, se há uma atribuição de variáveis que torna a fórmula verdadeira. Uma instância de exemplo, onde "∧" indica "não", pode ser:

(x₁ ∨ ¬ x₃) ∧ (¬ x₂ ∨ x₃) ∧ (¬ x₁ ∨ ¬ x₂)

Inclusões

Sabe-se que NL está contida em P, uma vez que existe um algoritmo de tempo-polinomial para 2-satisfatibilidade, mas não se sabe se NL = P ou se L = NL. Sabe-se que NL = co-NL, onde co-NL é o complemento de NL. Este resultado foi descoberto independentemente por Neil Immerman e Róbert Szelepcsényi em 1987 (Teorema Immerman-Szelepcsényi), que recebeu o Prêmio Gödel de 1995 por este trabalho.

Na complexidade de circuito, NL pode ser colocada dentro da hierarquia NC. Em Papadimitriou 1994, teorema 16.1, temos:

NC₁ ⊆ L ⊆ NL ⊆ NC₂

Mais precisamente, NL está contida em AC1. Sabe-se que NL é igual a ZPL, a classe de problemas solucionáveis por algoritmos aleatórios no espaço logarítmico e no tempo ilimitado, sem erro. Não se sabe, no entanto, ou acredita-se ser igual a RLP e ZPLP, as restrições de tempo polinomial de RL e ZPL que alguns autores se referem como RL e ZPL.

Podemos relacionar NL ao espaço determinístico usando o teorema de Savitch, que nos diz que qualquer algoritmo não-determinístico pode ser simulado por uma máquina determinística em no máximo mais espaço quadrático. Do teorema de Savitch, temos diretamente que:

NL ⊆ SPACE(log² n), equivalentemente a NL ⊆ L²

Esta foi a inclusão de espaço-determinístico conhecido como (Papadimitrou 1994, problema 16.4.10, "Espaço simétrico"). Como as classes de espaço maior não são afetadas pelo aumento quadrático, as classes não-determinísticas e determinísticas são conhecidas por serem iguais; por exemplo, temos PSPACE = NPSPACE.

Definição probabilística

Suponha que C é a classe de complexidade dos problemas solucionáveis em espaço logarítmico com máquinas de Turing probabilísticas que nunca aceitam incorretamente, mas estão autorizadas a rejeitar incorretamente menos de 1/3 do tempo, o que é chamado erro unilateral. A constante 1/3 é arbitrária, qualquer x com 0 ≤ x < 1/2 seria suficiente.

Acontece que C = NL. Nota-se que C, ao contrário de sua contrapartida L determinística, não se limita ao tempo polinomial, porque embora tenha um número polinomial de configurações, ele pode usar aleatoriedade para escapar de um loop infinito. Se nos limitarmos a tempo polinomial, obtemos a classe RL, que está contida em, mas não se sabe ou acredita-se ser igual a NL.

Existe um algoritmo simples que estabelece que C = NL. Claramente, C está contida em NL, desde que:

Se a cadeia não está na linguagem, ambos rejeitam todos os caminhos ao longo da computação;
Se a cadeia está na linguagem, um algoritmo NL aceita ao longo de pelo menos um caminho de computação; e um algoritmo C aceita ao longo de, pelo menos, dois terços dos seus caminhos de computação.

Para mostrar que NL está contida em C, nós simplesmente tomamos um algoritmo NL e escolhemos um caminho de computação aleatório de tamanho n, fazendo isso 2n vezes. Devido a nenhum caminho de computação exceder o tamanho n; e existirem 2n caminhos de computação em todos, temos uma boa chance de atingir a aceitação (limitada inferiormente por uma constante).

O único problema é que não temos espaço no espaço-logarítmico para um contador binário que vai até 2ⁿ. Para contornar isso, nós o substituímos por um contador aleatório, que simplesmente vira n moedas; e para ou rejeita se todos os lados derem cara. Uma vez que esse evento tem probabilidade 2^-n, nós esperamos levar 2ⁿ passos em média antes de parar. Ele só precisa manter rodando o número total de caras que vê em uma fileira, o qual pode ser em espaço-logarítmico.

Assim, quando olharmos apenas para o espaço por si só, parece que aleatoriedade e não-determinismo são igualmente poderosos.

Complexidade descritiva

Há uma simples caracterização lógica de NL: Ela contém precisamente aquelas linguagens expressas em lógica de primeira ordem com um operador de fecho transitivo adicionado.

Bibliografia

Papadimitriou, C. (1994). "Chapter 16: Logarithmic Space". Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1.
Michael Sipser (1997). "Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL". Introduction to the Theory of Computation. PWS Publishing. pp. 294–302. ISBN 0-534-94728-X.
Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Our C is what Goldreich calls badRSPACE(log n).