PSPACE

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

PSPACE est un objet de théorie de la complexité, un domaine de l'informatique théorique. C'est une classe de complexité c'est-à-dire un ensemble de problèmes de décision.

Plus précisément, c'est l'ensemble des problèmes de décision qui peuvent se résoudre sur une machine de Turing déterministe avec un espace polynomial.

Définition formelle[modifier | modifier le code]

Si l'on appelle \mbox{SPACE}(t(n)), l'ensemble de tous les problèmes qui peuvent être résolus par des machines de Turing déterministes utilisant un espace O(t(n)) pour une fonction t en la taille de l'entrée n, alors on peut définir PSPACE formellement par :

\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{SPACE}(n^k) \ .

Liens avec les autres classes[modifier | modifier le code]

Complexity subsets pspace.svg

Comme l'illustre l'image de droite, on a les inclusions suivantes : NP \scriptstyle\subseteq PSPACE \scriptstyle\subseteq EXPTIME.

De plus le théorème de Savitch[1] indique que PSPACE=NPSPACE, c'est-à-dire qu'en espace polynomial, les machines déterministes et non déterministes ont la même expressivité.

Puis par le théorème d'Immerman-Szelepcsényi, PSPACE=coNPSPACE.

Un autre résultat est le fait que PSPACE contienne la hiérarchie polynomiale : PH \subseteq PSPACE.

Le théorème de Shamir donne aussi, dans le contexte des systèmes de preuve interactive, que IP = PSPACE[2].

Problèmes complets[modifier | modifier le code]

Quantified boolean formula[modifier | modifier le code]

Le problème Quantified boolean formula (QBF) est le problème complet canonique pour la classe PSPACE.

Une formule QBF (Quantified Boolean Formula) est une formule de la forme : Q_1x_1Q_2x_2...Q_nx_n\varphi(x_1,x_2,...,x_3) où les Q_i sont des quantificateurs (\forall ou \exists) et les x_i sont des variables booléennes. On remarque qu'une telle formule est vraie ou fausse.

Le problème QBF est :

  • Entrée : Une formule QBF \psi.
  • Question : \psi est-elle vraie ?

Si l'on prend le point de vue des langages, le langage QBF, est celui des formules QBF vraies.

Expressions rationnelles[modifier | modifier le code]

Le problème qui consiste, étant donné une expression rationnelle à savoir si elle génère tous les mots possible, est PSPACE-complet[3]

Jeux[modifier | modifier le code]

Dans certains jeux, savoir l'on peut gagner, étant donné une certaine situation est PSPACE-complet. Par exemple certaines versions de hex, du morpion ou de Othello.

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]

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

  1. Walter Savitch, « Relationships between nondeterministic and deterministic tape complexities », Journal of Computer and System Sciences, vol. 4, no 2,‎ 1972
  2. Adi Shamir, « IP = PSPACE », Journal of the ACM, vol. 39, no 4,‎ octobre 1992, p. 869-877 (IP = PSPACE lire en ligne)
  3. H. B., III Hunt, « On the time and tape complexity of languages. I », dans Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973),‎ 1973 (lire en ligne), p. 10-19.