Pour les algorithmes, la mémoire est une ressource bien plus puissante que le temps

La version originale de cette histoire est parue dans Quanta Magazine .

Un après-midi de juillet 2024, Ryan Williams entreprit de prouver qu'il avait tort. Deux mois s'étaient écoulés depuis qu'il avait fait une découverte surprenante sur la relation entre temps et mémoire en informatique. C'était l'ébauche d'une preuve mathématique que la mémoire était plus puissante que ne le croyaient les informaticiens : une petite quantité de mémoire serait aussi utile que beaucoup de temps dans tous les calculs imaginables. Cela lui semblait si improbable qu'il en déduisit que quelque chose clochait, et il mit rapidement la preuve de côté pour se concentrer sur des idées moins farfelues. Il avait enfin trouvé le temps de trouver l'erreur.

Ce n'est pas ce qui s'est passé. Après avoir passé des heures à étudier son argumentation, Williams n'a trouvé aucune faille.

« Je pensais juste perdre la tête », a déclaré Williams, informaticien théoricien au Massachusetts Institute of Technology. Pour la première fois, il a commencé à envisager la possibilité que, peut-être, la mémoire soit aussi puissante que ses travaux le laissaient entendre.

Au cours des mois qui ont suivi, il a approfondi les détails, examiné chaque étape et sollicité les commentaires de quelques autres chercheurs. En février, il a finalement publié sa preuve en ligne , et a été largement salué.

« C'est incroyable. C'est magnifique », a déclaré Avi Wigderson , informaticien théoricien à l'Institute for Advanced Study de Princeton, dans le New Jersey. Dès qu'il a appris la nouvelle, Wigderson a envoyé un courriel de félicitations à Williams. Objet : « Tu m'as époustouflé. »

Le temps et la mémoire (aussi appelés espace) sont les deux ressources les plus fondamentales du calcul : chaque algorithme prend un certain temps à s'exécuter et nécessite de l'espace pour stocker les données pendant son exécution. Jusqu'à présent, les seuls algorithmes connus pour accomplir certaines tâches nécessitaient un espace à peu près proportionnel à leur temps d'exécution, et les chercheurs ont longtemps pensé qu'il n'y avait pas moyen de faire mieux. La preuve de Williams a établi une procédure mathématique permettant de transformer n'importe quel algorithme, quel qu'il soit, en une forme utilisant beaucoup moins d'espace.

De plus, ce résultat – une affirmation sur ce que l'on peut calculer dans un certain espace – implique également un second résultat, sur ce que l'on ne peut pas calculer dans un certain laps de temps. Ce second résultat n'est pas surprenant en soi : les chercheurs s'attendaient à ce qu'il soit vrai, mais ils ne savaient pas comment le prouver. La solution de Williams, fondée sur son premier résultat radical, paraît excessivement caricaturale, comparable à prouver la culpabilité d'un meurtrier présumé en établissant un alibi en béton pour tous les autres habitants de la planète. Elle pourrait également offrir une nouvelle façon de s'attaquer à l'un des plus anciens problèmes ouverts de l'informatique.

« C'est un résultat assez étonnant et une avancée considérable », a déclaré Paul Beame , informaticien à l'Université de Washington. « C'est un peu moins surprenant que ce soit Ryan qui réalise cela. »

Williams, 46 ans, a un visage ouvert et expressif et une touche de gris dans les cheveux. Son bureau, qui donne sur les flèches colorées du Stata Center du MIT, illustre une fois de plus l'utilisation créative de l'espace. Deux tapis de yoga ont transformé un rebord de fenêtre en coin lecture improvisé, et le bureau est niché dans un coin aux formes étranges, libérant ainsi la place pour un canapé face à un grand tableau blanc débordant de gribouillages mathématiques.

Le MIT est bien loin de la maison d'enfance de Williams, dans l'Alabama rural, où l'espace ne manquait pas. Il a grandi dans une ferme de 20 hectares et a vu un ordinateur pour la première fois à l'âge de 7 ans, lorsque sa mère l'a conduit à travers le comté pour un cours de perfectionnement scolaire. Il se souvient avoir été fasciné par un programme simple permettant de générer un feu d'artifice numérique.

« Il s'agissait de prendre une couleur au hasard et de l'envoyer dans une direction aléatoire depuis le centre de l'écran », explique Williams. « On ne pouvait pas prédire l'image qu'on allait obtenir. » Le monde de l'informatique lui semblait un terrain de jeu fantastique et débordant de possibilités infinies. Le jeune Williams était conquis.

« J'écrivais des programmes sur papier, destinés à être exécutés sur un futur ordinateur », a-t-il expliqué. « Mes parents ne savaient pas vraiment quoi faire de moi. »

En grandissant, Williams est passé des ordinateurs imaginaires aux ordinateurs réels. Pour ses deux dernières années de lycée, il a intégré l'Alabama School of Math and Science, un prestigieux internat public, où il a découvert l'aspect théorique de l'informatique.

« J'ai réalisé qu'il existait un monde plus vaste et qu'il était possible de penser mathématiquement les ordinateurs », a-t-il déclaré. « C'est ce que je voulais faire. »

Williams était particulièrement attiré par une branche de l'informatique théorique appelée théorie de la complexité computationnelle. Cette théorie étudie les ressources (temps et espace) nécessaires à la résolution de problèmes informatiques tels que le tri de listes ou la factorisation de nombres. La plupart des problèmes peuvent être résolus par de nombreux algorithmes différents, chacun ayant ses propres exigences en termes de temps et d'espace. Les théoriciens de la complexité classent les problèmes en catégories, appelées classes de complexité, en fonction des ressources requises par les algorithmes les plus performants pour les résoudre, c'est-à-dire les algorithmes les plus rapides ou les moins gourmands en espace.

Mais comment rendre l'étude des ressources informatiques mathématiquement rigoureuse ? Vous n'irez pas loin en essayant d'analyser le temps et l'espace en comparant des minutes à des mégaoctets. Pour progresser, il est essentiel de commencer par les bonnes définitions.

Ces définitions sont issues des travaux de Juris Hartmanis, un informaticien pionnier qui savait se débrouiller avec des ressources limitées. Né en 1928 dans une famille lettone aisée, son enfance fut bouleversée par le déclenchement de la Seconde Guerre mondiale. Les forces d'occupation soviétiques arrêtèrent et exécutèrent son père. Après la guerre, Hartmanis termina ses études secondaires dans un camp de réfugiés. Il entra ensuite à l'université, où il excella malgré le manque de moyens pour acheter des manuels scolaires.

« Je compensais en prenant des notes très détaillées pendant les cours », se souvient-il lors d'une interview en 2009. « Il y a un avantage certain à improviser et à surmonter les difficultés. » Hartmanis immigra aux États-Unis en 1949 et enchaîna les petits boulots – construction de machines agricoles, fabrication d'acier et même majordome – tout en étudiant les mathématiques à l'Université de Kansas City. Il poursuivit ensuite une carrière fulgurante dans le domaine naissant de l'informatique théorique.

En 1960, alors qu'il travaillait au laboratoire de recherche de General Electric à Schenectady, dans l'État de New York, Hartmanis rencontra Richard Stearns, un étudiant diplômé effectuant un stage d'été. Dans deux articles révolutionnaires , ils établirent des définitions mathématiques précises du temps et de l'espace. Ces définitions fournirent aux chercheurs le langage nécessaire pour comparer les deux ressources et classer les problèmes en classes de complexité.

L'une des classes les plus importantes porte le nom modeste de « P ». En gros, elle englobe tous les problèmes pouvant être résolus dans un délai raisonnable. Une classe de complexité analogue pour l'espace est appelée « PSPACE ».

La relation entre ces deux classes est l'une des questions centrales de la théorie de la complexité. Chaque problème de P se trouve également dans PSPACE, car les algorithmes rapides n'ont tout simplement pas assez de temps pour occuper beaucoup d'espace dans la mémoire d'un ordinateur. Si l'affirmation inverse était également vraie, les deux classes seraient équivalentes : l'espace et le temps auraient une puissance de calcul comparable. Mais les théoriciens de la complexité soupçonnent que PSPACE est une classe beaucoup plus vaste, contenant de nombreux problèmes qui ne sont pas de P. Autrement dit, ils pensent que l'espace est une ressource de calcul bien plus puissante que le temps. Cette croyance découle du fait que les algorithmes peuvent utiliser indéfiniment le même petit morceau de mémoire, tandis que le temps est moins indulgent : une fois écoulé, il est irrécupérable.

« L'intuition est tellement simple », a déclaré Williams. « On peut réutiliser l'espace, mais pas le temps. »

Mais l'intuition ne suffit pas aux théoriciens de la complexité : ils veulent des preuves rigoureuses. Pour prouver que PSPACE est supérieur à P, les chercheurs devraient démontrer que, pour certains problèmes de PSPACE, les algorithmes rapides sont catégoriquement impossibles. Par où commencer ?

Il se trouve qu'ils ont débuté à l'Université Cornell, où Hartmanis s'est installé en 1965 pour diriger le nouveau département d'informatique. Sous sa direction, celui-ci est rapidement devenu un centre de recherche en théorie de la complexité et, au début des années 1970, deux chercheurs, John Hopcroft et Wolfgang Paul, ont entrepris d'établir un lien précis entre le temps et l'espace.

Hopcroft et Paul savaient que pour résoudre le problème P versus PSPACE, ils devaient prouver que certains calculs ne peuvent pas être effectués en un temps limité. Or, il est difficile de prouver une hypothèse négative. Ils ont donc décidé d'inverser le problème et d'explorer les possibilités offertes par un espace limité. Ils espéraient prouver que des algorithmes disposant d'un certain budget spatial peuvent résoudre les mêmes problèmes que des algorithmes disposant d'un budget temporel légèrement supérieur. Cela indiquerait que l'espace est au moins légèrement plus puissant que le temps – une étape modeste, mais nécessaire, pour démontrer que PSPACE est supérieur à P.

Dans cet objectif, ils se sont tournés vers une méthode que les théoriciens de la complexité appellent simulation. Cette méthode consiste à transformer des algorithmes existants en de nouveaux algorithmes résolvant les mêmes problèmes, mais avec des espaces et des temps différents. Pour comprendre l'idée de base, imaginez qu'on vous donne un algorithme rapide pour classer votre bibliothèque par ordre alphabétique, mais qu'il vous oblige à disposer vos livres en dizaines de petites piles. Vous préférerez peut-être une approche plus compacte, même si elle prend plus de temps. Une simulation est une procédure mathématique permettant d'obtenir un algorithme plus adapté : utilisez l'algorithme original et vous obtiendrez un nouvel algorithme qui économise de l'espace au détriment du temps.

Les concepteurs d'algorithmes étudient depuis longtemps ces compromis espace-temps pour des tâches spécifiques comme le tri. Mais pour établir une relation générale entre temps et espace, Hopcroft et Paul avaient besoin d'une solution plus complète : une procédure de simulation peu encombrante, applicable à tous les algorithmes, quel que soit le problème qu'ils résolvent. Ils s'attendaient à ce que cette généralité ait un prix. Une simulation universelle ne peut exploiter les détails d'un problème spécifique ; elle ne permettra donc probablement pas de gagner autant d'espace qu'une simulation spécialisée. Mais lorsque Hopcroft et Paul ont commencé leurs travaux, il n'existait aucune méthode universelle connue pour gagner de l'espace. Même une petite économie constituerait un progrès.

La percée a eu lieu en 1975, après que Hopcroft et Paul se soient associés à un jeune chercheur nommé Leslie Valiant . Le trio a mis au point une procédure de simulation universelle qui économise toujours un peu d'espace. Quel que soit l'algorithme utilisé, vous obtiendrez un équivalent dont le budget d'espace est légèrement inférieur au budget temps de l'algorithme d'origine.

« Tout ce qu'on peut faire en si peu de temps, on peut aussi le faire dans un espace légèrement plus restreint », a déclaré Valiant. C'était la première étape majeure dans la quête de connexion entre l'espace et le temps.

Mais les progrès ont ensuite stagné, et les théoriciens de la complexité ont commencé à soupçonner qu'ils se heurtaient à un obstacle fondamental. Le problème résidait précisément dans le caractère universel de la simulation de Hopcroft, Paul et Valiant. Si de nombreux problèmes peuvent être résolus avec beaucoup moins d'espace que de temps, certains semblaient intuitivement nécessiter presque autant d'espace que de temps. Si tel était le cas, des simulations universelles plus efficaces en termes d'espace seraient impossibles. Paul et deux autres chercheurs ont rapidement prouvé que c'était effectivement impossible , à condition de poser une hypothèse apparemment évidente : différents blocs de données ne peuvent pas occuper simultanément le même espace mémoire.

« Tout le monde tenait pour acquis qu’on ne pouvait pas faire mieux », a déclaré Wigderson.

Les résultats de Paul suggéraient que résoudre le problème P versus PSPACE nécessiterait d'abandonner complètement la simulation au profit d'une approche différente, mais personne n'avait de bonnes idées. Le problème est resté là pendant 50 ans, jusqu'à ce que Williams finisse par débloquer la situation.

Il devait d’abord terminer ses études à l’université.

En 1996, le moment est venu pour Williams de postuler à des universités. Il savait que poursuivre des études en théorie de la complexité l'emmènerait loin de chez lui, mais ses parents lui ont clairement fait comprendre que la côte Ouest et le Canada étaient hors de question. Parmi les options qui lui restaient, Cornell s'est imposée à lui par sa place prépondérante dans l'histoire de sa discipline de prédilection.

« Ce type, Hartmanis, a défini les classes de complexité temporelle et spatiale », se souvient-il avoir pensé. « C'était important pour moi. »

Williams fut admis à Cornell grâce à une aide financière généreuse et arriva à l'automne 1997, déterminé à tout faire pour devenir lui-même théoricien de la complexité. Sa détermination marqua ses camarades.

« Il était tout simplement passionné par la théorie de la complexité », a déclaré Scott Aaronson , informaticien à l'Université du Texas à Austin, qui a travaillé avec Williams à Cornell.

Mais en deuxième année, Williams peinait à suivre les cours qui privilégiaient la rigueur mathématique à l'intuition. Après avoir obtenu une note moyenne dans un cours de théorie informatique, son professeur lui a suggéré d'envisager d'autres carrières. Mais Williams ne voulait pas abandonner son rêve. Il a redoublé d'efforts et s'est inscrit à un cours de théorie de troisième cycle, espérant qu'une excellente note dans ce cours plus difficile ferait bonne impression sur ses candidatures aux études supérieures. Le professeur qui enseignait ce cours était Hartmanis, alors un expert chevronné dans le domaine.

Williams commença à assister chaque semaine aux séances de Hartmanis, où il était presque toujours le seul étudiant présent. Sa ténacité fut récompensée : il obtint une mention A et Hartmanis accepta de le conseiller sur un projet de recherche indépendant le semestre suivant. Leurs rencontres hebdomadaires se poursuivirent tout au long de ses études universitaires. Hartmanis l'encouragea à cultiver une approche individuelle de la recherche sur la complexité et l'éloigna avec douceur des impasses.

« J'ai été profondément influencé par lui à l'époque », a déclaré Williams. « Je pense que je le suis encore aujourd'hui. »

Malgré l'obtention d'une bourse de recherche convoitée de la National Science Foundation, Williams a été rejeté par tous les programmes de doctorat auxquels il a postulé. Apprenant la nouvelle, Hartmanis a téléphoné à un collègue, puis s'est retourné et a félicité Williams pour son admission dans un programme de master d'un an à Cornell. Un an plus tard, Williams a de nouveau postulé à divers programmes de doctorat et, fort de cette expérience de recherche supplémentaire, il a réussi.

Williams a continué à travailler sur la théorie de la complexité pendant ses études supérieures et les années qui ont suivi. En 2010, quatre ans après l'obtention de son doctorat, il a réalisé un résultat marquant – un petit pas, mais le plus important depuis des décennies – vers la résolution de la question la plus célèbre de l'informatique théorique : la nature des problèmes complexes. Ce résultat a consolidé la réputation de Williams, qui a ensuite écrit des dizaines d'autres articles sur différents sujets liés à la théorie de la complexité.

P versus PSPACE n'en faisait pas partie. Williams était fasciné par ce problème depuis sa première rencontre à l'université. Il avait même complété son cursus d'informatique par des cours de logique et de philosophie, cherchant l'inspiration dans d'autres perspectives sur le temps et l'espace, en vain.

« J'y ai toujours pensé », a déclaré Williams. « Je n'avais rien d'assez intéressant à dire à ce sujet. »

L’année dernière, il a finalement trouvé l’opportunité qu’il attendait.

L'histoire du nouveau résultat de Williams a débuté avec des progrès sur une autre question concernant la mémoire en calcul : quels problèmes peuvent être résolus avec un espace extrêmement limité ? En 2010, Stephen Cook, pionnier de la théorie de la complexité, et ses collaborateurs ont inventé une tâche, appelée « problème d'évaluation arborescente » , dont ils ont prouvé l'impossibilité pour tout algorithme disposant d'un budget d'espace inférieur à un seuil spécifique. Mais il y avait une faille. La preuve reposait sur la même hypothèse de bon sens que Paul et ses collègues avaient formulée des décennies plus tôt : les algorithmes ne peuvent pas stocker de nouvelles données dans un espace déjà saturé.

Pendant plus d'une décennie, les théoriciens de la complexité ont tenté de combler cette lacune. Puis, en 2023, James, le fils de Cook , et un chercheur nommé Ian Mertz ont ouvert le feu en concevant un algorithme qui résolvait le problème de l'évaluation arborescente en utilisant beaucoup moins d'espace qu'on ne l'aurait cru possible. La preuve de Cook père supposait que les bits de données étaient comme des cailloux devant occuper des emplacements distincts dans la mémoire d'un algorithme. Mais il s'avère que ce n'est pas la seule façon de stocker des données. « On peut en fait considérer ces cailloux comme des choses que l'on peut écraser légèrement les unes sur les autres », a déclaré Beame.

L'algorithme de Cook et Mertz a suscité la curiosité de nombreux chercheurs, mais ses applications au-delà du problème d'évaluation des arbres n'étaient pas évidentes. « Personne n'avait perçu à quel point il était crucial pour le temps par rapport à l'espace lui-même », a déclaré Wigderson.

Ryan Williams était l'exception. Au printemps 2024, un groupe d'étudiants a présenté l'article de Cook et Mertz dans le cadre de leur projet de fin d'études dans un cours qu'il enseignait. Leur enthousiasme l'a incité à s'y intéresser de plus près. Dès qu'il l'a fait, une idée lui est venue. La méthode de Cook et Mertz, a-t-il réalisé, était en réalité un outil polyvalent pour réduire l'utilisation de l'espace. Pourquoi ne pas l'utiliser pour alimenter une nouvelle simulation universelle reliant le temps et l'espace, comme celle conçue par Hopcroft, Paul et Valiant, mais en mieux ?

Ce résultat classique était un moyen de transformer n'importe quel algorithme disposant d'un budget temporel donné en un nouvel algorithme doté d'un budget spatial légèrement inférieur. Williams a constaté qu'une simulation basée sur des cailloux mous réduirait considérablement l'utilisation de l'espace par le nouvel algorithme, à peu près égale à la racine carrée du budget temporel de l'algorithme initial. Ce nouvel algorithme, plus efficace en termes d'espace, serait également beaucoup plus lent ; la simulation était donc peu susceptible d'avoir des applications pratiques. Mais d'un point de vue théorique, c'était tout simplement révolutionnaire.

Pendant 50 ans, les chercheurs ont supposé qu'il était impossible d'améliorer la simulation universelle de Hopcroft, Paul et Valiant. Si l'idée de Williams fonctionnait, elle ne se contenterait pas de battre leur record, elle le démolirait.

« J'y ai réfléchi et je me suis dit : "Eh bien, c'est tout simplement impossible" », a déclaré Williams. Il a mis l'idée de côté et n'y est revenu qu'en ce jour fatidique de juillet, où il a tenté de trouver la faille dans l'argumentation, sans succès. Après avoir constaté l'absence de faille, il a passé des mois à écrire et réécrire la preuve pour la rendre aussi claire que possible.

Fin février, Williams a finalement mis en ligne l'article final . Cook et Mertz étaient aussi surpris que tout le monde. « J'ai dû faire une longue marche avant de faire quoi que ce soit d'autre », a déclaré Mertz.

Valiant a eu un aperçu de l'amélioration de Williams par rapport à son résultat vieux de plusieurs décennies lors de son trajet matinal. Il a enseigné pendant des années à l'Université Harvard, à deux pas du bureau de Williams au MIT. Ils s'étaient déjà rencontrés, mais ils ignoraient qu'ils habitaient le même quartier jusqu'à ce qu'ils se croisent dans le bus par une journée enneigée de février, quelques semaines avant la publication du résultat. Williams a décrit sa preuve à Valiant, surpris, et a promis de lui envoyer son article.

« J'ai été très, très impressionné », a déclaré Valiant. « Si vous obtenez un résultat mathématique qui soit le meilleur depuis 50 ans, c'est que vous faites forcément quelque chose de bien. »

Avec sa nouvelle simulation, Williams avait démontré un résultat positif concernant la puissance de calcul de l'espace : les algorithmes utilisant relativement peu d'espace peuvent résoudre tous les problèmes nécessitant un temps légèrement supérieur. Puis, en quelques lignes de calcul, il a inversé la tendance et démontré un résultat négatif concernant la puissance de calcul du temps : au moins quelques problèmes ne peuvent être résolus sans utiliser plus de temps que d'espace. Ce deuxième résultat, plus restreint, est conforme aux attentes des chercheurs. Le plus étrange est la façon dont Williams y est parvenu : en prouvant d'abord un résultat applicable à tous les algorithmes, quels que soient les problèmes qu'ils résolvent.

« J'ai encore du mal à y croire », a déclaré Williams. « Cela semble trop beau pour être vrai. »

Exprimé en termes qualitatifs, le deuxième résultat de Williams pourrait ressembler à la solution longtemps recherchée au problème P versus PSPACE. La différence est une question d'échelle. P et PSPACE sont des classes de complexité très larges, tandis que les résultats de Williams fonctionnent à un niveau plus fin. Il a établi un écart quantitatif entre la puissance de l'espace et celle du temps, et pour prouver que PSPACE est plus grand que P, les chercheurs devront considérablement élargir cet écart.

C'est un défi de taille, comparable à celui de percer une fissure de trottoir avec un pied-de-biche jusqu'à ce qu'elle atteigne la largeur du Grand Canyon. Mais il serait possible d'y parvenir en utilisant une version modifiée de la procédure de simulation de Williams, qui répéterait l'étape clé plusieurs fois, économisant ainsi un peu d'espace à chaque fois. C'est comme augmenter la longueur de son pied-de-biche à plusieurs reprises : s'il est suffisamment grand, on peut tout ouvrir. Cette amélioration répétée ne fonctionne pas avec la version actuelle de l'algorithme, mais les chercheurs ignorent s'il s'agit d'une limitation fondamentale.

« Cela pourrait être un goulot d'étranglement majeur, ou un goulot d'étranglement de 50 ans », a déclaré Valiant. « Ou bien, ce pourrait être un problème que quelqu'un pourrait résoudre la semaine prochaine. »

Si le problème est résolu la semaine prochaine, Williams s'en voudra. Avant de rédiger son article, il a passé des mois à tenter, sans succès, d'étendre ses résultats. Mais même si une telle extension est impossible, Williams est convaincu que la poursuite de l'exploration spatiale mènera forcément à des résultats intéressants, peut-être à des progrès sur un tout autre problème.

« Je n'arrive jamais à prouver précisément ce que je veux prouver », a-t-il déclaré. « Mais souvent, ce que je prouve est bien meilleur que ce que je voulais. »

Note de l'éditeur : Scott Aaronson est membre du conseil consultatif du magazine Quanta.

Article original reproduit avec la permission de Quanta Magazine , une publication éditoriale indépendante de la Fondation Simons dont la mission est d'améliorer la compréhension publique de la science en couvrant les développements et les tendances de la recherche en mathématiques et en sciences physiques et de la vie.