Découverte révolutionnaire : réduction drastique de l’espace nécessaire au calcul

Ryan Williams, informaticien au MIT, a fait une découverte révolutionnaire, infirmant 50 ans de suppositions sur le compromis entre l’espace et le temps de calcul. La théorie traditionnelle affirmait qu’un calcul de t étapes nécessite environ t bits de mémoire. Williams a cependant prouvé que tout problème résoluble en temps t ne nécessite qu’environ √t bits de mémoire. Cette réussite repose sur la réduction du problème à un problème équivalent qui réutilise intelligemment l’espace, comprimant ainsi l’information. La recherche suggère que le goulot d’étranglement du calcul n’est pas la capacité de mémoire, mais son utilisation efficace.