Loading AI tools
Da Wikipédia, a enciclopédia livre
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.
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².
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.