En teoria de la complexitat, el Teoremoa de Savitch, provat per Walter Savitch el 1970 dona la relació entre complexitats espacials deterministes i no deterministes. Diu que per cada funció Dit d'altre manera, si una màquina de Turing no determinista pot resoldre un problema usant un espai f(n), una màquina de Turing ordinària (determinista) pot resoldre el mateix problema amb el quadrat del dit espai.
Corol·laris del teorema Es dedueixen importants corol·laris a partir del teorema:
PSPACE = NPSPACE Se segueix directament del fet que el quadrat d'una funció polinòmica segueix sent una funció polinòmica. Es creu que no existeix una relació similar entre les classes polinòmiques P i NP, tot i que és encara una qüestió oberta. NL ⊆ L² Ja que
Referències
Savitch Categoria:Complexitat computacional