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 \Omega (\log(n))$

${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\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 ${\displaystyle {\mathsf {\color {Blue}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right)}$