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

Corollaire[modifier | modifier le code]

Un corollaire important est l'égalité des classes polynomiales en espace : PSPACE = NPSPACE.

Bibliographie[modifier | modifier le code]

  • Walter Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, no 2,‎ 1972

Notes et références[modifier | modifier le code]