Teorema de Savitch

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ó

$f\in \mathrm{\Omega }(\log (n))$

$𝖭𝖲𝖯𝖠𝖢𝖤\left(f\left(n\right)\right)\subseteq 𝖣𝖲𝖯𝖠𝖢𝖤\left({\left(f\left(n\right)\right)}^2\right)$

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 ${𝖫}^2=𝖣𝖲𝖯𝖠𝖢𝖤\left({(\log n)}^2\right)$