Théorème de Savitch

Un article de Wikipédia, l'encyclopédie libre.
Ceci est la version actuelle de cette page, en date du 1 octobre 2019 à 12:52 et modifiée en dernier par Fschwarzentruber (discuter | contributions). L'URL présente est un lien permanent vers cette version.
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

  • 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[modifier | modifier le code]

  1. a et b 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 »).