PSPACE

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

En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité 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 des problèmes de décision décidés 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 définit 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 \scriptstyle\subseteq EXPSPACE.

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 PSPACE-complets[modifier | modifier le code]

A l'instar de la NP-complétude, on peut définir la notion de problèmes PSPACE-complets. Un problème est PSPACE-dur si tout problème dans PSPACE s'y réduit en temps polynomial. Un problème PSPACE-complet si il est dans PSPACE et il est PSPACE-dur.

Formules booléennes quantifiées[modifier | modifier le code]

Une formule booléenne quantifiée (abrégé QBF pour 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. Si une telle formule est close, alors elle est vraie ou fausse.

Le problème QBF-SAT (satisfiabilité d'une formule booléenne quantifiée), aussi appelé TQBF (pour true quantified Boolean formula) est :

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

Le problème QBF-SAT est le problème complet canonique pour la classe PSPACE. Il est PSPACE-complet.

Universalité des langages réguliers[modifier | modifier le code]

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

Jeux[modifier | modifier le code]

Dans certains jeux, savoir si l'on peut gagner étant donné une certaine situation du jeu, est PSPACE-complet. Par exemple certaines versions de hex, du morpion ou de Othello ont cette propriété. De façon plus général, certains auteurs considèrent qu'un des concepts centraux de PSPACE est le fait de pouvoir définir une stratégie optimale pour les jeux à deux joueurs avec information parfaite[4].

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,‎
  2. Adi Shamir, « IP = PSPACE », Journal of the ACM, vol. 39, no 4,‎ , p. 869-877 (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),‎ (lire en ligne), p. 10-19.
  4. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A modern Approach, Cambridge University Press,‎ (ISBN 0-521-42426-7), chap. 4.2.2 (« The essence of PSPACE: optimum strategies for game-playing »)