Teorema de Savitch
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 ideia 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.
