Théorème de Savitch

Walter Savitch a démontré ce théorème dans sa thèse de master sous la direction de Stephen Cook[1]. Il a été publié dans un article de recherche dans le Journal of Computer and System Sciences en 1972[2]. Des idées de la preuve étaient déjà présentes dans un article de Philip Lewis, Juris Hartmanis et Richard Stearns publié en 1965[1].

Le théorème stipule que pour toute fonction ƒ(n) ≥ log(n),

${\displaystyle {\text{NSPACE}}\left(f\left(n\right)\right)\subseteq {\text{DSPACE}}\left(f^{2}\left(n\right)\right).}$En d'autres termes, tout problème décidable sur une machine de Turing non-déterministe en espace ƒ(n), l'est également sur une machine de Turing déterministe en espace ƒ²(n).

Considérons un problème décidable par une machine de Turing M non-déterministe en espace ƒ(n). La démonstration consiste à se ramener un problème d'accessibilité dans le graphe des configurations de la machine M. On donne ensuite un algorithme récursif basé sur diviser pour régner qui utilise un espace ƒ²(n) pour le résoudre[3].

Un corollaire important est l'égalité des classes polynomiales en espace : PSPACE = NPSPACE. Il en va de même pour les classes exponentielles en espace : EXPSPACE = NEXPSPACE.

• Walter Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, n^o 2,‎ 1972
• (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 4 (« Space complexity »)