Théorème de Savitch

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Histoire[modifier | modifier le code]

Le théorème est dû à Walter Savitch qui l'a démontré dans sa thèse de master sous la direction de Stephen Cook[1]. Il a été publié en journal 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),

Preuve[modifier | modifier le code]

La preuve consiste à ramener le problème à un problème d'accessibilité dans le graphe des configurations d'une machine, puis à donner un algorithme récursif basé sur diviser pour régner qui utilise peu d'espace 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 »).