Une conjecture de 50 ans sur l'espace versus le temps en informatique résolue

Une question centrale de la théorie de la complexité computationnelle est la relation entre P et PSPACE, des classes englobant les problèmes résolubles en temps et en espace raisonnables, respectivement. Intuitivement, l'espace est une ressource plus puissante que le temps car il est réutilisable. Pendant 50 ans, les chercheurs ont tenté de prouver que PSPACE est plus grand que P, ce qui signifie que certains problèmes sont impossibles à résoudre rapidement, mais résolubles avec un espace limité. Hopcroft, Paul et Valiant ont fait une découverte en 1975, montrant que l'espace est légèrement plus puissant que le temps. Cependant, ce progrès a été limité par l'approche de 'simulation'. Ryan Williams a finalement brisé l'impasse avec une approche novatrice, résolvant le problème de longue date.