Teorema de Immerman–Szelepcsényi: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 20h33min de 3 de dezembro de 2011

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.

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.

Links externos

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

@@ Linha 4: / Linha 4: @@
 Em outras palavras, uma [[Máquina de Turing não determinística|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 (complexidade)|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, 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, 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 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á caminho de s para v de tamanho ≤ i}. Em outras palavras, Ai incluirá todos os vértices que são alcançáveis a partir de s em 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, logo <G,s,t>  ∈ ¬CAM.
-Lema: Um algoritmo pode ser construído tal que dado ri, ele enumerará vértices em Ai e ACEITA em espaço logarítmico. Note que se o ri fornecido for maior que o número real de vértices de Ai, então o algoritmo REJEITA; entretanto, se ri é menor que o número real de vértices em Ai, o algoritmo ACEITA mas enumeraria apenas um subconjunto de Ai.
- ENUMERAR(s,i,r_i,G)
-: Contador := 0
-: Para todo vértice v em G
-:    Não deterministicamente ou CONTINUE ou adivinhe um caminho de tamanho menor ou igual a i, de s para v
-:    Contador := Contador + 1
-:    Output v
-:    IF Contador ≥ r_i
-:       ACEITA
-: REJEITA
-ENUMERAR percorre todos os vértices do grafo G em espaço logarítmico, pois a representação de cada nó e do Contador requere somente log |G| bits e não-deterministicamente selecionar um caminho também necessita de somente espaço logarítmico.
-Agora, com ENUMERAR a disposição é possível computar o real ri em espaço logarítmico usando um algoritmo que é baseado no princípio matemático de indução. Ao usar ENUMERAR como uma sub-rotina, substitua ACEITA em ENUMERAR com RETURN e deixe REJEITE como REJEITE.
-Obviamente r0 = 1, pois Ai inclui somente o vértice s.
-Agora, assuma que ri é dado. Então ri+1 pode ser calculado pelo seguinte algoritmo de espaço log.
- INDUCTIVE-COUNTING (s,i,r_i,G)
-: r := 1
-: Para todo vértice v ≠ s:
-:    Para cada u tal que(u,v) é uma aresta de G
-:       ENUMERAR (s,i,r_i,G)
-:       IF u é dado alguma vez como saída
-:          r := r + 1
-:          BREAK
-: Output r
-Esse algoritmo primeiro leva em conta o vértice inicial s, e depois percorre todos os vértices v do grafo G. Nas linhas 3–6 o algoritmo tenta encontrar um vértice u em Ai diretamente conectado ao vértice v, simulando ENUMERAR. Se tal vértice é encontrado, isto  significa que v está em Ai+1, e por isso o resultado é incrementado de uma unidade para levar em conta esse vértice. Note que o algoritmo não precisa armazenar toda a saída de ENUMERAR toda vez que ela é chamada como uma sub-rotina. Ele pode armazenar apenas um vértice por vez e checar se u aparece alguma vez na saída. Portanto, esse algoritmo roda em espaço logarítmico.
-Com esse algoritmo a disposição nós podemos desenvolver um algoritmo para st-não-conectividade consistindo de duas partes. A primeira parte computaria rn começando com r0 = 1 e a partir daí usando INDUCTIVE-COUNTING n − 1 vezes. Na segunda parte do algoritmo apenas simulamos ENUMERAR com o rn computado e se t é alguma vez dado como saída, isso significa que ele pode ser alcançado a partir de v, e o algoritmo REJEITA.
- NOT-CONNECTED (G,s,t)
-: r_n := 1;
-: FOR i := 1 TO n
-:    r_n := INDUCTIVE-COUNTING (s,i,r_n,G)
-: ENUMERAR (s,n,r_n,G)
-: IF t estiver alguma vez na saída
-:    REJEITA
-: ELSE
-:    ACEITA
-Esse algoritmo roda em espaço logarítmico, pois nós precisamos de log |G| bits para armazenar i e rn. Como foi mostrado acima,os algoritmos ENUMERAR e INDUCTIVE-COUNTING também rodam espaço logarítmico e novamente nós não precisamos armazenar toda a saída de ENUMERAR na linha 4, mas precisamos apenas checar se t é alguma vez dado como saída. Portanto, NOT-CONNECTED pode decidir se não há caminho do vértice s pra o vértice t em espaço logarítmico. Desta feita st-não-conectividade está em NL. Como nós conseguimos reduzir cada problema em NL para st-conectividade e cada problema em co-NL para st-não-conectividade nós 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 de st-conectividade. Analogamente nós podemos transformar qualquer co-linguagem no problema da st-não-conectividade. Ambos os grafos teriam 2<sup>''O''(''s''(''n''))</sup> vértices se L ∈ NSPACE(s(n)). Portanto, podemos decidir tanto a alcançabilidade quanto a não-alcançabilidade do estado de aceitação em log(2<sup>''O''(''s''(''n''))</sup>)&nbsp;=&nbsp;''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==