P vs. PSPACE : L’espace est-il computationnellement plus puissant que le temps ?

Une question centrale en théorie de la complexité est la relation entre les classes de complexité P et PSPACE. P englobe les problèmes résolubles en un temps raisonnable, tandis que PSPACE traite de la complexité spatiale. La croyance dominante est que PSPACE est plus grand que P, en raison de la réutilisabilité de l’espace, contrairement au temps. Pour le prouver, il faudrait démontrer que certains problèmes dans PSPACE sont insolubles en temps polynomial. L’article relate la percée de 1975 de Hopcroft, Paul et Valiant, montrant le léger avantage de l’espace sur le temps, mais les progrès ont stagné. Le travail de Ryan Williams a finalement brisé l’impasse, offrant de nouvelles perspectives pour résoudre le problème P vs. PSPACE.