Teorema de Immerman–Szelepcsényi

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde dezembro de 2011)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

Na teoria de complexidade computacional, o teorema de Immerman–Szelepcsényi foi provado de forma independente por Neil Immerman e Róbert Szelepcsényi no ano de 1987. Por tal prova ambos dividiram o prêmio Gödel de 1995. Em sua forma geral, o teorema afirma que NSPACE(s(n)) = co-NSPACE(s(n)) para qualquer função s(n) ≥ log n. Esse resultado pode ser considerado de forma equivalente como NL = co-NL, apesar de esse ser um caso especial no qual s(n) = log n. Tal caso especial implica o teorema geral por um argumento de "padding".[carece de fontes?]

Em outras palavras, uma máquina de Turing não-determinística consegue resolver um problema e o seu complemento com a mesma quantidade assintótica de espaço. Não há resultado semelhante no que tange as classes de complexidade de tempo, e inclusive há conjecturas de que NP não é igual a co-NP.

Prova[editar | editar código-fonte]

Teorema: Seja s(n) ≥ log n qualquer função, então NSPACE[s(n)] = co-NSPACE[s(n)].

O primeiro passo é demonstrar que NL = co-NL. Isso pode ser alcançado ao tomar o problema da st-conectividade (NL-completo), e mostrando que o seu complemento (st-não-conectividade) também está em NL.

Definição: O problema da st-conectividade é descrito formalmente no livro Introdução à Teoria da Computação de Michael Sipser (versão traduzida) pela seguinte linguagem simbólica:

        CAM = {〈G = <V,E>, s, t〉 | G é um grafo direcionado que tem um caminho direcionado de s para t}.

Dado um grafo direcionado G com n vértices, e os nós s e t em G, o problema da st-não-conectividade (¬CAM) é o problema de se determinar se não há caminho entre os vértices s e t.

       ¬CAM = {〈G = <V,E>, s, t〉 | G é um grafo direcionado que não tem caminho direcionado de s para t}.

Para ilustrar o fato de que ¬CAM está em NL, podemos construir um algoritmo não-determinístico que, em espaço logarítmico, decide se dois determinados vértices não estão conectados por um caminho direcionado.

Para provar a corretude de tal algoritmo, devemos mostrar duas coisas:

  • Se as escolhas não-determinísticas são feitas corretamente e s e t estão desconectados, então o algoritmo aceita.
  • Se s e t estão conectados, independentemente de qual escolhas não determinísticas adotemos, o algoritmo rejeita. Isto é, todos os

ramos da computação não-determinística rejeitam.

Aqui estão as ideias centrais da prova para a segunda condição:

Suponha por absurdo que s e t estão conectados e o algoritmo aceita. Para manter o adversário controlando o não-determinismo de forma "honesta", o algoritmo é construído de forma que se o não-determinismo for não cooperativo, o algoritmo rejeita no final da sub-rotina ENUMERAR. Portanto como nós assumimos que o algoritmo aceita, o não-determinismo deve ter sido cooperativo, o que implica pelo design do algoritmo que nós deveríamos ter rejeitado, temos portanto uma contradição.

Primeiro, defina Ai como segue: Ai = {v: há um caminho de s para v de tamanho ≤ i}. Em outras palavras, Ai incluirá todos os vértices alcançáveis a partir de s com i ou menos saltos. Seja ri = |Ai|. Note que se t não está em An−1, onde n = |V|, então não há caminho de s para t em G, i.e., \langle G,s,t\rangle ∈ st-não-conectividade.

Lema: Pode ser construído um algoritmo de tal forma que dado ri, enumerará os vértices em Ai e ACEITA em espaço logarítmico. Note que se o ri dado é maior que o número real de vértices em Ai, então o algoritmo REJEITA; entretanto, se ri for menor do que o número real de vértices em Ai o algoritmo ACEITA mas enumera apenas um subconjunto de Ai.

ENUMERA(s,i,r_i,G)
1: Cont := 0
2: FOR ALL vértices v em G
3:    Não-deterministicamente ou CONTINUE ou adivinhe um caminho de tamanho menor que ou igual a i, de s para v
4:    Cont := Cont + 1
5:    Retorne v
6:    IF Cont ≥ r_i
7:       ACEITA
8: REJEITA

ENUMERA percorre todos os vértices do grafo G em espaço logarítmico, pois a representação de cada vértice e do contador Cont requere apenas log |G| bits e selecionar não-deterministicamente um caminho também só requere espaço logarítmico.

Agora, que temos a rotina ENUMERA à nossa disposição é possível calcular o valor de ri em espaço logarítmico usando um algoritmo que é baseado no princípio da indução matemática. Ao usar ENUMERA como uma sub-rotina, substitua ACEITA em ENUMERA por RETURN e deixe REJEITA como REJEITA.

Obviamente r0 = 1, já que Ai inclui somente o vértice s.

Agora, se ri for fornecido, ri+1 pode ser calculado pelo seguinte algoritmo de espaço logarítmico:

INDUCTIVE-COUNTING (s,i,r_i,G)
1: r := 1
2: FOR ALL vértices v ≠ s:
3:    FOR EACH u tal que (u,v) é uma aresta em G
4:       ENUMERA (s,i,r_i,G)
5:       IF u for dado alguma vez como saída
6:          r := r + 1
7:          BREAK
8: Retorne r

Esse algoritmo primeiro considera o vértice inicial s, e posteriormente percorre todos os outros vértices v do grafo G. Nas linhas 3–6 o algoritmo tenta achar, simulando ENUMERA, um vértice u em Ai, diretamente conectado ao vértice v. Se tal vértice é encontrado, isso significa que v está em Ai+1, logo o resultado é incrementado para levar esse vértice em consideração. Note que o algoritmo não precisa armazenar toda saída de ENUMERA toda vez que essa sub-rotina é chamada. Ele pode apenas armazenar um vértice por vez e checar se u alguma vez é dado como saída. Desta feita, o algoritmo roda em espaço logarítmico.

Com tal algoritmo á nossa disposição, podemos desenvolver um algoritmo para st-não-conectividade em duas partes. A primeira parte calcularia rn começando com r0 = 1 e depois usando INDUCTIVE-COUNTING n − 1 vezes. Na segunda parte o algoritmo apenas simularia ENUMERA com o valor calculado de rn e se t for alguma vez dado como saída, isso comprova que ele pode ser alcançado por v, e o algoritmo REJEITA.

NÃO-CONECTADO (G,s,t)
1: r_n := 1;
2: FOR i := 1 TO n
3:    r_n := INDUCTIVE-COUNTING (s,i,r_n,G)
4: ENUMERA (s,n,r_n,G)
5: IF t é dado alguma vez como saída
6:    REJEITA
8: ELSE
9:    ACEITA

Esse algoritmo roda em espaço logarítmico, afinal nós precisamos de log |G| bits para guardar i e rn. Como foi mostrado previamente, os algoritmos ENUMERA e INDUCTIVE-COUNTING também rodam em espaço logarítmico e novamente não precisamos armazenar toda saída de ENUMERA na linha 4. Apenas necessitamos checar se t é alguma vez dado como saída. Desta feita, NÃO-CONECTADO pode decidir se não existe caminho do vértice s para t em espaço logarítmico. Temos então que st-não-conectividade ( ¬CAM) está em NL. Como podemos reduzir todo problema em NL para st-conectividade e todo problema em co-NL para st-não-conectividade concluímos que NL = co-NL.

Agora, para s(n) ≥ log n nós podemos transformar as computações de qualquer máquina de Turing não determinística M sobre uma linguagem L, em um grafo de seus estados e simular M usando o algoritmo da st-conectividade. Analogamente podemos transformar qualquer co-linguagem no problema da st-não-conectividade problem. Ambos os grafos teriam 2O(s(n)) vértices se L ∈ NSPACE(s(n)). Desta forma, podemos decidir tanto alcançabilidade quanto não alcançabilidade do estado de aceitação, em log(2O(s(n))) = O(s(n)) space e NSPACE(s(n)) = co-NSPACE(s(n)).

Hierarquia de espaço logarítmico[editar | editar código-fonte]

Como um corolário, no mesmo artigo, Immerman provou que, usando a igualdade da complexidade descritiva entre NL e FO(Transitive Closure), a hierarquia logarítmica, i.e. as linguagens decididas por máquinas de Turing alternantes em espaço logarítmico com um número limitado de alternações, está na mesma classe que NL.

Referências[editar | editar código-fonte]

  • N. Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17, 1988, pp. 935–938.
  • R. Szelepcsényi, The method of forcing for nondeterministic automata, Bulletin of the EATCS 33, 1987, pp. 96–100.
  • M. Sipser, Introduction to the theory of computation, tradução da segunda edição norte-americana, 2007

Ligações externas[editar | editar código-fonte]