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(ƒ ) ⊆ DSPACE( ²).
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. 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: Uma relação similar, mas que ainda não foi provada é para casos de complexidade em tempo
