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.