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),

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, no 2,‎
  • (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (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, no 2,‎
  3. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5 (« Théorème de Savitch »).
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.