Classe NSPACE

Définition

La classe NSPACE contient les problèmes résolus par un algorithme non déterministe en utilisant un espace polynomial.

$$NSPACE=\{Q\mid \text{il existe un algorithme non deˊterministe utilisant }O(n^k)\text{ espace pour }Q\}$$

Théorème

Théorème de Savitch (1970)
$NSPACE=PSPACE$

Cela signifie que le non-déterminisme n’apporte aucun avantage quand on mesure la complexité en espace.

Exemple

• Résolution non déterministe de SAT avec mémoire bornée
• Recherche de chemin dans un graphe avec pile limitée