Théorème de Savitch

Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique. Il a été prouvé par Walter Savitch en 1970 et donne une relation entre les classes de complexité en espace, déterministes et non-déterministes. Une conséquence importante est que NPSPACE = PSPACE, c'est-à-dire, tout problème décidable sur une machine non-déterministe en espace polynomial, l'est aussi sur une machine déterministe en espace polynomial.

Histoire

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].

Énoncé du théorème

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 ƒ^2(n).

Démonstration

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 ƒ^2(n) pour le résoudre[3].

Égalités de classes en espace

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.

Bibliographie

• 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 »)

Notes et références

1. Richard J. Lipton, « Savitch’s Theorem », sur Gödel's Lost Letter.
2. Walter Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, n^o 2,‎ 1972
3. Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5 (« Théorème de Savitch »).