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.

Énoncé du théorème[modifier | modifier le code]

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

\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(f^2\left(n\right)\right).

Preuve[modifier | modifier le code]

La preuve consiste à ramener le problème à un problème de connexité (ou accessibilité) dans un graphe, puis à donner un algorithme récursif utilisant peu d'espace pour le résoudre[1].

Corollaire[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.

Histoire[modifier | modifier le code]

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

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. Sylvain Perifel, Complexité algorithmique, Ellipses,‎ , 432 p. (ISBN 9782729886929, lire en ligne), chap. 4.5 (« Théorème de Savitch »).
  2. a et b Richard J. Lipton, « Savitch’s Theorem », sur Gödel's Lost Letter.
  3. Walter Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, no 2,‎