Teorema de Immerman–Szelepcsényi

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

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 A_i como segue: A_i = {v: há um caminho de s para v de tamanho ≤ i}. Em outras palavras, A_i incluirá todos os vértices alcançáveis a partir de s com i ou menos saltos. Seja r_i = |A_i|. Note que se t não está em A_n−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 r_i, enumerará os vértices em A_i e ACEITA em espaço logarítmico. Note que se o r_i dado é maior que o número real de vértices em A_i, então o algoritmo REJEITA; entretanto, se r_i for menor do que o número real de vértices em A_i o algoritmo ACEITA mas enumera apenas um subconjunto de A_i.

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 r_i 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 r₀ = 1, já que A_i inclui somente o vértice s.

Agora, se r_i for fornecido, r_i+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 A_i, diretamente conectado ao vértice v. Se tal vértice é encontrado, isso significa que v está em A_i+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 r_n começando com r₀ = 1 e depois usando INDUCTIVE-COUNTING n − 1 vezes. Na segunda parte o algoritmo apenas simularia ENUMERA com o valor calculado de r_n 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 r_n. 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 2^O(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(2^O(s(n))) = O(s(n)) space e NSPACE(s(n)) = co-NSPACE(s(n)).

Hierarquia de espaço logarítmico

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

• 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

• Lance Fortnow, Foundations of Complexity, Lesson 19: The Immerman–Szelepcsenyi Theorem. Acessado em 9 de setembro de 2009.