La classe PSPACE

1. Présentation



Dans la théorie de la complexité, la notion de classe est utilisée afin de classer les différents problèmes par rapport à la complexité de ceux-ci.
Cette classe, classant les problèmes par rapport à l’espace mémoire qu’ils nécessitent, contient l’ensemble des problèmes pouvant être résolus par un algorithme déterministe en utilisant un espace mémoire polynomial par rapport à la taille des données.




2. Représentation graphique



Il est possible de représenter graphiquement la classe PSPACE avec les deux graphes suivants qui représentent les courbes f(n) = n2 et f(n) = n6 :








3. La class P



Cette classe, classant les problèmes par rapport au temps, est surement la plus importante de la théorie des complexités car elle contient tous les problèmes facilement solubles. Elle contient réellement tous les problèmes pouvant être résolus par un algorithme déterministe en un temps polynomial par rapport à la taille des données. Cela signifie que la taille des données est n, le temps sera nx.
Le problème avec cette classe est qu’elle peut tout à fait contenir des problèmes rapidement solvables comme elle peut contenir des problèmes qui nécessitent un temps très important. En effet, la complexité en temps pourra être n100000 pour un problème de la classe P comme elle pourra être n2.
Il est possible de déduire l’inclusion P inclut PSPACE car les algorithmes nécessitant un temps polynomial ne peuvent que nécessiter un espace polynomial.



4. Extension a NPSPACE



Le théorème de Savitch (1970) énonce que si une machine de Turing nondéterministe peut résoudre un problème en utilisant un espace mémoire f(n) (<= log(n)), alors une machine de Turing déterministe peut résoudre le même problème avec un espace mémoire f2(n).
Ce théorème permet de déduire le corollaire : PSPACE = NPSPACE. Autrement dit, PSPACE correspond à l’ensemble des problèmes pouvant être résolus par une machine de Turing déterministe ou non-déterministe avec un espace mémoire polynomial par rapport à la taille des données. Ce corollaire est évident car le carré d’une fonction polynomial est une fonction polynomial.
PSPACE correspond à l’ensemble des problèmes pouvant être résolus par une machine de Turing déterministe ou non-déterministe avec un espace mémoire polynomial par rapport à la taille des données. Ce corollaire est évident car le carré d’une fonction polynomial est une fonction polynomial.