Complexidade NL
Na teoria da complexidade, NL é 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.
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: (x1 ∨ ¬ x3) ∧ (¬ x2 ∨ x3) ∧ (¬ x1 ∨ ¬ x2)
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: 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:
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: 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).
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.
