# 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".$^[$
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:
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.
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 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$_0$ = 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:
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$_0$ = 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.
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.