Classe PSPACE

Définition

La classe PSPACE contient les problèmes qui peuvent être résolus avec un espace mémoire polynomial, indépendamment du temps nécessaire.

$$PSPACE=,Q\mid Q\text{ est reˊsoluble avec un espace polynomial }O(n^k),$$

Un algorithme peut donc prendre exponentiellement longtemps, mais il n’utilise qu’une quantité polynomiale de mémoire.

Exemples

• QBF (Quantified Boolean Formula)
• Jeux à information parfaite (échecs sur un plateau fini)
• SAT appartient à PSPACE (car on peut le résoudre par parcours exhaustif sans dépasser un espace polynomial)

Propriétés

• $P\subseteq NP\subseteq PSPACE$
• $PSPACE=NPSPACE$ (théorème de Savitch)
• $NP\subseteq PSPACE$ (montré en CM7)

Problèmes PSPACE-complets

Un problème est PSPACE-complet s’il est :

1. Dans PSPACE
2. PSPACE-difficile (tout problème de PSPACE s’y réduit)

Exemple : QSAT (SAT quantifié)