Nouvel horizon de la recherche sur les algorithmes : démonstration qu’« un peu de mémoire peut être plus puissant que beaucoup de temps »

• Une nouvelle démonstration du théoricien de l’informatique du MIT Ryan Williams montre que la mémoire peut être une ressource de calcul plus puissante que le temps
• Elle met fin à 50 ans de stagnation sur la relation entre complexité en temps et en espace et présente une méthode permettant de transformer n’importe quel algorithme pour qu’il utilise moins de mémoire
• Le cœur de la démonstration consiste à généraliser la simulation économe en espace, avec l’idée de réduire l’usage mémoire d’un algorithme jusqu’à l’ordre de la racine carrée du temps
• Cela marque un progrès vers une démonstration quantitative de la différence entre les classes PSPACE et P, et ouvre aussi la possibilité d’établir un écart plus large
• Les experts jugent cette avancée comme un « développement étonnant et le point de départ d’une nouvelle exploration », qui pourrait aider à résoudre d’autres problèmes difficiles de l’informatique théorique

---

One Small Step for Space, One Giant Leap for Complexity

Aperçu de la nouvelle démonstration de Ryan Williams

• À l’été 2024, Ryan Williams, du MIT, relisait sa démonstration lorsqu’il a compris qu’une idée qu’il croyait erronée était en réalité valable
• Il a proposé une procédure générale permettant de transformer tout algorithme pour qu’il s’exécute avec moins de mémoire
• Cela permet de prouver que certains problèmes ne peuvent pas être résolus avec un temps limité

Temps et espace : les deux ressources du calcul

• Tout algorithme utilise du temps et de la mémoire (espace)
• Jusqu’ici, on considérait que, pour résoudre certains problèmes, l’espace était proportionnel au temps
• La démonstration de Williams établit mathématiquement que l’espace peut être plus puissant que le temps

Origines et histoire de l’informatique théorique

• Juris Hartmanis et Richard Stearns ont posé dans les années 1960 les définitions de la complexité en temps et en espace
• Ils ont jeté les bases de la classification des problèmes en classes de complexité selon les ressources nécessaires pour les résoudre
• P désigne les problèmes résolubles en un temps raisonnable, PSPACE ceux résolubles avec une quantité raisonnable de mémoire

Première avancée : la technique de simulation de 1975

• Hopcroft, Paul et Valiant ont développé une procédure universelle de simulation capable de transformer n’importe quel algorithme pour qu’il utilise un peu moins d’espace
• Cela a constitué un premier pas pour éclairer le lien entre temps et espace, mais les progrès se sont ensuite heurtés à une limite
• On pensait qu’il était impossible d’aller plus loin à cause de l’hypothèse selon laquelle des données ne peuvent pas occuper simultanément le même espace

Le tournant : Squishy Pebbles

• En 2010, le pionnier de la théorie de la complexité Stephen Cook et ses collègues ont conçu le problème de l’évaluation d’arbre - Pebbles and Branching Programs for Tree Evaluation et ont démontré qu’il était impossible à résoudre pour des algorithmes disposant d’un budget mémoire inférieur à un certain seuil
  • Mais il y avait une faille. Cette démonstration reposait sur la même hypothèse de bon sens que celle formulée des décennies plus tôt par Paul et ses collègues
  • À savoir qu’un algorithme ne peut pas stocker de nouvelles données dans un espace déjà plein
  • Pendant plus de dix ans, les théoriciens de la complexité ont cherché à combler cette faille
• James Cook, le fils de Stephen Cook, et Ian Mertz ont publié en 2023 un algorithme pour le problème d’évaluation d’arbre qui brise cette hypothèse : Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• Ils ont proposé un nouveau modèle de représentation dans lequel les données en mémoire peuvent se superposer physiquement
• Cette approche est devenue la clé pour dépasser les limites des simulations existantes

Le saut décisif de Williams

• Après avoir découvert la technique de Cook-Mertz grâce à une présentation d’étudiants, Williams a eu l’idée de l’appliquer à la simulation universelle
• La nouvelle simulation permet de réduire les besoins en espace d’un algorithme jusqu’à l’ordre de la racine carrée du temps
• Il a publié la version finale de son article sur arXiv en février 2025, où elle a reçu les éloges du monde académique

Ce que signifie ce résultat

• Cette démonstration ne prouve pas directement que PSPACE > P, mais constitue une avancée décisive qui crée une “ouverture” dans cette direction
• Si cette procédure peut à l’avenir être appliquée de façon répétée pour creuser un écart plus important, il deviendra possible de se rapprocher d’une résolution du problème P vs PSPACE
• Cela pourrait fournir un point d’appui pour résoudre l’un des plus anciens problèmes ouverts de l’informatique

Une conclusion marquante

• Williams a ainsi résumé son résultat :
  « Je n’ai pas réussi à prouver ce que je voulais vraiment démontrer, mais ce que j’ai finalement prouvé est encore meilleur que ce que j’espérais. »

[nunojay]

....Hein ?

[GN⁺]

Avis Hacker News

• En laissant de côté le flou (fuzz), une machine de Turing multitape qui s’exécute en temps t peut être simulée en utilisant un espace O(sqrt(t log t)) (en général avec un temps d’exécution supérieur à t) Simulating Time With Square-Root Space
  • Il est dommage que les articles de Quanta mêlent trop souvent des formulations poétiques ou exagérées en mathématiques, ce qui prête à confusion. L’article de Quanta dit que « certaines tâches nécessitaient un espace proportionnel à leur temps d’exécution », mais même la simple hiérarchie de complexité ne mène pas à une telle intuition générale. On ne peut pas construire une intuition d’ensemble à partir d’« quelques algorithmes » seulement
  • Je trouve presque insultant, peut-être par excès de pédagogie envers le lecteur, que Quanta décrive la classe de complexité P uniquement comme « tous les problèmes qu’on peut résoudre en un temps raisonnable » sans même employer le terme polynomial
• Il y a cette phrase dans le « Camel Book », imprégné de la philosophie Perl : « Si vous manquez de mémoire, vous pouvez en acheter ; si vous manquez de temps, il n’y a rien à faire. » J’adore ce livre, simplement parce qu’il est amusant
  • Mais cette phrase a aussi un envers : un programme qui demande plus de mémoire que l’ordinateur n’en a ne peut pas tourner du tout, alors qu’un programme lent peut malgré tout s’exécuter un jour ou l’autre ; le temps reste donc lui aussi une ressource cruciale
• La victoire des tables de consultation (lookup tables) où l’on stocke des valeurs pré-calculées. Autrefois, je me disais que si l’on pouvait centralement stocker tous les calculs, au point de ne presque plus avoir besoin de processeur, la vitesse de traitement pourrait être révolutionnée (même s’il reste bien sûr le problème distinct de la recherche rapide)
  • Quand j’ai commencé à travailler dans les systèmes de stockage, j’avais proposé l’idée de pré-calculer et stocker à l’avance tous les blocs de 4 Ko ; je me souviens avoir été sidéré quand on m’a fait remarquer que le nombre de blocs de 4 Ko distincts dépasse le nombre d’atomes dans l’univers
  • L’algorithme HashLife fait quelque chose d’assez similaire dans le Game of Life de Conway, de façon Turing-complète. J’ai trouvé fascinant qu’on puisse pré-calculer en quelque sorte des états futurs par sauts, même face à des états très complexes et variés
  • Petite blague : il n’y a aucun problème à appliquer aussi la mise en cache à la recherche elle-même
  • En pratique, c’est déjà mis en œuvre à travers le cache à l’échelle de la communauté, c’est-à-dire la distribution de logiciels précompilés. Même les barrières traditionnelles qui forçaient à renoncer à certaines fonctionnalités de langage faute de pouvoir compiler efficacement peuvent être surmontées avec la compilation parallèle dans le cloud et des caches mondiaux. Si l’on compile une fois au moment de la sortie, tout le monde peut ensuite en profiter
  • Dans le prolongement de l’idée « si tout calcul était stocké au centre, on n’aurait plus besoin de processeur », on pourrait carrément mémoriser aussi l’historique des recherches
• À cause du style poétique de Quanta, j’ai du mal à comprendre si cette recherche s’applique réellement à des ordinateurs concrets, ou s’il s’agit seulement d’un scénario purement théorique. Je me demande si cela veut dire qu’en utilisant plus de mémoire, l’ordinateur devient plus lent
• Je fais de la programmation graphique raster depuis longtemps, et l’usage des tables de consultation m’est devenu instinctif. Récemment, j’ai développé un outil serveur qui pré-enregistre diverses formes dans une base de données afin d’utiliser, à chaque requête, un résultat optimisé. C’est un schéma simple et intuitif. Je ne l’ai pas appris spécialement auprès d’un professeur du MIT ; c’était juste une manière de travailler acquise par la pratique, alors voir une preuve de sa validité mathématique me rend assez fier. J’ai l’impression que beaucoup de savoir-faire algorithmique vient en fait de l’expérience des praticiens (par exemple : l’algorithme du winding number)
  • Les gains que j’obtiens ces jours-ci en optimisant des jeux viennent tous d’une manière contextuelle de manipuler des tables de consultation. Une table de consultation n’a pas besoin d’être un tableau statique ; des données qui évoluent légèrement dans le temps peuvent aussi être exploitées de cette façon. Cela m’a ouvert les yeux sur le traitement côté GPU, et il est très efficace d’envoyer au GPU, comme une texture, des tables qui étaient créées statiquement à la compilation ou à l’exécution, en n’en modifiant qu’une partie pendant le runtime. La frontière de ce qu’on appelle une table de consultation devient floue
• Il me semble intuitif que l’espace (la mémoire) puisse représenter bien plus de résultats que le temps. Sur une bande de longueur n, on peut écrire pendant O(n) temps, mais si la bande est binaire, il existe 2^n configurations de longueur n. Si l’on utilise bien l’espace, on obtient une expressivité bien supérieure à celle du temps
  • Mon intuition : une seule cellule peut contenir le résultat intermédiaire de centaines de calculs. Si l’on ne peut pas stocker ces résultats intermédiaires et qu’il faut tout recalculer à chaque fois, l’efficacité chute énormément. Une situation avec 0 % de hit cache est très rare, et dans la plupart des cas on peut améliorer l’efficacité en exploitant l’espace. En revanche, il est difficile de remplacer l’espace de centaines de cellules par une seule unité de temps, et dans les architectures de calcul actuelles, un SIMD infini est impossible
  • On tient trop facilement pour acquise l’hypothèse d’un accès aléatoire à la mémoire en O(1), alors qu’en réalité, à mesure que l’ordinateur grossit, le coût d’accès peut monter jusqu’à O(n^(1/3)). C’est quelque chose qu’on ressent très concrètement dans les data centers. Je crois que ce n’était pas le modèle UMA, mais un autre
  • Tant que P ≠ PSPACE n’est pas démontré, c’est un domaine où il est plus difficile d’établir les choses mathématiquement que de s’appuyer sur l’intuition
  • D’un autre côté, c’est peut-être vrai, mais pour des problèmes difficiles à paralléliser (par ex. alternating machine PTIME=PSPACE), un grand espace ne procure pas forcément un avantage décisif. Dans l’article, le saut de t/log t à sqrt(t log t) est révolutionnaire, mais il existera sans doute des limites substantielles qu’on ne pourra pas dépasser même avec une parallélisation infinie
  • En pratique, cela dépend de la nature du travail : quand l’accès au stockage est bien plus lent qu’une affectation, il peut être plus rapide de recalculer
• Cette « relation inverse » entre temps et espace peut s’expliquer par le fait que lorsqu’on borne une ressource, on ne peut pas automatiquement obtenir l’optimum de l’autre. Par exemple, dans les algorithmes de tri, si l’on impose trois contraintes — temps, espace et stabilité —, le fait d’exiger en plus la stabilité peut dégrader l’efficacité en temps ou en espace. À ce jour, il n’existe pas de tri stable aussi rapide et aussi peu gourmand en mémoire que les meilleurs tris instables
• J’aime personnellement le style des articles de Quanta Magazine. Ils élargissent la perspective non seulement des informaticiens, mais aussi du grand public intéressé par ces domaines. Leur vue d’ensemble et leur ton accessible peuvent susciter de nouvelles idées et de nouveaux angles de réflexion
• Je partage des liens vers une conférence et un article de Ryan Williams
• Si une machine de Turing à bande unique reçoit en entrée un entier binaire N et doit écrire N fois le symbole 1 à droite sur la bande, il semble qu’il lui faille N cases d’espace en temps N. Alors comment peut-on simuler cela avec moins de N espace ? Et compte tenu du fait qu’une machine de Turing ne peut pas sauter arbitrairement à une position de la bande, je me demande aussi quel lien cela a réellement avec un ordinateur concret
  • Une machine de Turing multitape est bien plus rapide qu’une machine à bande unique, et l’« espace » dont on parle ici désigne l’espace de travail temporaire, hors entrée/sortie
  • L’article traite principalement de problèmes de décision et ne considère que des situations où la sortie n’est qu’un seul bit. Si la sortie faisait N bits, ce serait en pratique équivalent à concaténer N problèmes de décision