Teorema de Savitch

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na teoria da complexidade computacional, o teorema de Savitch, provado por Walter Savitch em 1970, afirma que para toda função ƒ(n) ≥ log(n),

   NSPACE(ƒ(n)) ⊆ DSPACE((ƒ(n))²).

em outras palavras, se uma máquina de Turing não-determinística pode resolver um problema usando um espaço f(n) (polinomial), uma máquina de Turing determinística ordinária pode resolver o mesmo problema dentro dessa região delimitada. Embora não-determinismo possa produzir aumento exponencial de tempo, esse teorema mostra que o mesmo não ocorre na requisição de espaço.

Prova[editar | editar código-fonte]

A prova do teorema é construtiva: exibe um algoritmo para CAM, o problema de determinar se existe um caminho entre dois vértices de um grafo orientado, que é executado em espaço O((log n)²) para n vértices. A idéia básica do algoritmo é resolver recursivamente um problema mais geral, testando a existência de um caminho de um vértice s até um outro vértice t que usa no máximo k vértices, onde k é um parâmetro de entrada do algoritmo recursivo; CAM pode ser resolvido fazendo k = n. Para testar um caminho de k-vértices entre s e t, testa-se primeiro se o vértice u pode ser ponto intermediário, recursivamente procurando por caminhos da metade do comprimento entre s e u e entre u e t.

Em pseudocódigo:

   def k-edge-path(s,t,k):
       if k == 0:
           return s == t
       else if k == 1:
           return (s,t) in edges
       else for u in vertices:
           if k-edge-path(s,u,⎣k/2⎦) and k-edge-path(u,t,⎡k/2⎤):
               return true
       return false

Essa busca chama a si mesmo até uma profundidade recursiva de O(log n) níveis, cada qual requer O(log n) bits para armazenar os parâmetros da função e as variáveis locais naquele nível, logo o espaço total usado pelo algoritmo é de O((log n)²). Embora descrito acima em uma linguagem de alto-nível, o mesmo algoritmo pode ser implementado em uma máquina de Turing. Como CAM é NL-completo, isso demonstra que todas as linguagens em NL também são da classe de complexidade DSPACE((log n)²). Que é comummente abreviado por L².

Corolários[editar | editar código-fonte]

Alguns corolários importantes do teorema incluem:

   • PSPACE = NPSPACE
       o Isso deriva do fato de que o quadrado de uma função polinomial ainda é uma função polinomial.

Uma relação similar, mas que ainda não foi provada é para casos de complexidade em tempo

         polinomial, P e NP.
   • NL ⊆ L²
       o Resultado direto da construção da prova.

Ver também[editar | editar código-fonte]

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

  • Sipser, Michael (1997), "Section 8.1: Savitch's Theorem", Introduction to the Theory of Computation, PWS Publishing, pp. 279–281, ISBN 0-534-94728-X.
  • Papadimitriou, Christos (1993), "Section 7.3: The Reachability Method", Computational Complexity (1st ed.), Addison Wesley, pp. 149–150, ISBN 0-201-53082-1.
  • Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences 4 (2): 177–192, doi:10.1016/S0022-0000(70)80006-X.