Le 26 octobre 2026, OpenAI a publié un article de 67 pages, rédigé par un modèle interne non nommé, qui affirme réfuter l’hypothèse du temps exponentiel (ETH, pour Exponential Time Hypothesis). Russell Impagliazzo et Ramamohan Paturi ont formulé cette conjecture en 1999. Selon OpenAI, « des centaines d’articles » s’appuient sur elle pour établir, sous réserve qu’elle soit vraie, la difficulté de problèmes de théorie des graphes, de bases de données ou de biologie computationnelle. D’après l’annonce d’OpenAI, le modèle a trouvé la réfutation le 16 octobre, et une version vérifiée par Lean, un assistant de preuve, était prête le lendemain.
Impagliazzo et Paturi, tous deux à l’université de Californie à San Diego, dirigent avec Ryan Williams (MIT) le groupe chargé d’examiner la réfutation annoncée de leur propre hypothèse. La même publication revendique deux autres résultats : une preuve de la conjecture de lissage local de Sogge en toute dimension et une preuve d’existence de la théorie de Yang-Mills et de la chromodynamique quantique (QCD), qui couvre une partie d’un problème du prix du millénaire.
Le plancher de 3-SAT
3-SAT est le problème difficile de référence en informatique. Une formule y impose des contraintes portant chacune sur trois variables booléennes (vrai ou faux) ; il s’agit de savoir si une même affectation de valeurs les satisfait toutes. Essayer toutes les affectations demande 2^n étapes pour n variables. Des décennies de travaux ont abaissé la base de cette exponentielle : environ (4/3)^n pour l’algorithme d’Uwe Schöning en 1999, 1,308^n pour la famille PPSZ dans un article de Timon Hertli en 2014, puis environ 1,307^n après des améliorations successives, la dernière dans une prépublication de Tao Jiang et Shaowei Cai en 2026.
L’ETH pose un plancher à ces progrès. Dans sa forme habituelle, elle affirme que 3-SAT exige un temps 2^(cn) pour une constante c fixe et strictement positive, quel que soit l’algorithme. Les théoriciens de la complexité s’en servent comme étalon : montrer qu’un algorithme rapide pour un problème X en donnerait un pour 3-SAT suffit, sous l’ETH, à établir que X est difficile. L’ETH implique que P et NP sont distincts : c’est un énoncé plus fort que P ≠ NP.
Le contenu de l’article
L’article, daté du 17 octobre et révisé le 25, décrit un algorithme déterministe qui compte les affectations satisfaisant une formule de ce type, pour toute largeur de clause fixée, en temps 2^(n/(log n)^(1/2+o(1))) à des facteurs polynomiaux près et avec une mémoire polynomiale. Un décompte supérieur à zéro signale qu’une solution existe : la borne vaut donc pour 3-SAT.
Ce temps de calcul croît plus vite que n’importe quel polynôme, mais son exposant rapporté au nombre de variables tend vers zéro quand n augmente, ce que l’ETH excluait. La preuve formelle, selon la page d’OpenAI qui en décrit le périmètre, couvre un comptage exact en temps 2^O(n(log log n)^2/√log n) : une borne un peu moins fine que la meilleure de l’article, mais toujours sous-exponentielle.
Trois résultats dans une seule publication
Le résultat de mathématiques porte sur les ondes. Christopher Sogge a proposé la conjecture de lissage local en 1991. Larry Guth, Hong Wang et Ruixiang Zhang l’ont démontrée en dimension deux en 2019, et Hong Wang et Joshua Zahl ont démontré la conjecture de Kakeya en dimension trois en 2025, travaux cités dans l’attribution de la médaille Fields 2026 à Hong Wang.
L’article de 59 pages d’OpenAI revendique une preuve du lissage local en toute dimension à partir de deux, dont découleraient les conjectures de Kakeya et de restriction. OpenAI dit avoir obtenu ce résultat le 18 octobre et l’avoir formalisé en Lean le lendemain. Ce mois-ci, trois équipes ont déposé des preuves d’une conjecture de géométrie vieille de 31 ans avec l’aide de l’IA.
Le résultat de physique, lui, n’est pas encore lisible par le public. L’entreprise affirme que ses modèles ont produit une preuve d’existence de la théorie de Yang-Mills pure le 9 septembre, puis de la QCD le 18 septembre, et qu’elle a achevé la formalisation Lean de l’existence de Yang-Mills le 16 octobre. Un groupe mené par David Gross, colauréat du prix Nobel de physique 2004, avec Michael Douglas, Arthur Jaffe, Igor Klebanov et Nikita Nekrasov, a « décidé de différer la publication des éléments produits par l’IA » et rédigera lui-même les résultats.
L’énoncé officiel du problème, rédigé par Jaffe et Edward Witten pour l’institut Clay, exige l’existence et un écart de masse (mass gap) ; OpenAI ne revendique que l’existence. Le 17 octobre, nous avions rapporté un précédent en physique : des contre-exemples trouvés par l’IA à une conjecture de 1967 sur la fusion.
Une campagne qui se compte en jours
OpenAI dit avoir commencé le 1er septembre à tester son modèle interne sur tous les problèmes du prix du millénaire encore ouverts. Le billet du 8 septembre date au 5 septembre la résolution revendiquée de Navier-Stokes, obtenue par « de l’ordre de 10 000 agents simultanés » environ 88 heures après le lancement, plus 17 heures pour la vérification Lean. OpenAI écrivait alors ne pas avoir l’intention de réclamer le prix.
Le 6 octobre, l’entreprise a mis en ligne sur GitHub des centaines de manuscrits. Le dépôt en compte aujourd’hui 721, répartis en 373 familles, avec environ 42 % des résultats principaux formalisés, et, selon OpenAI, un résultat a demandé en moyenne l’équivalent d’« environ trois heures de réflexion de ChatGPT Pro ». Scott Aaronson, spécialiste de la complexité à l’université du Texas à Austin, écrit sur son blog, Shtetl-Optimized, à propos de la réfutation de l’ETH : « Nous peinons encore à digérer les plats précédents, et le buffet continue sans fin ! » D’après le calendrier d’OpenAI, la réfutation de l’ETH est arrivée 45 jours après le 1er septembre, et la preuve du lissage local deux jours plus tard.
Qui vérifie la preuve ?
OpenAI présente ces manuscrits comme « une forme de données de recherche brutes » et a choisi une méthode de publication par discipline : le résultat mathématique est sorti tel quel, les fichiers sur l’ETH sont publics pendant qu’un groupe extérieur organise leur examen, et le groupe de physique décide seul de la publication. Selon les règles d’OpenAI, les participants ne signent aucun accord de confidentialité et ne sont pas payés ; l’entreprise dit ne revendiquer aucun crédit scientifique. Elle reconnaît que le choix de ces experts accompagnateurs « crée une asymétrie d’information ».
La lettre du groupe ETH à la communauté précise son rôle : « Notre participation ne doit pas être prise pour une certification de cette revendication. » Elle ajoute : « Si cette revendication est exacte, elle changera une part importante de l’informatique théorique. » Sur Bluesky, Williams a écrit que le groupe n’a pas accès aux modèles internes d’OpenAI, seulement au PDF, et qu’OpenAI a accepté ses deux demandes : rendre publiques toutes les données brutes et financer une conférence.
The Verge relève le calendrier : la veille de l’annonce, le 25 octobre, l’Advisory Group on Mathematics and Artificial Intelligence, un groupe indépendant de mathématiciens rattaché à l’Institute for Advanced Study de Princeton, recommandait sur le blog de Terence Tao aux entreprises d’IA de renoncer à désigner des mathématiciens pour recevoir les résultats de leurs modèles, en invoquant l’accès inégal, une sélection biaisée et une « réputation empruntée ». Le comité précise que ses conseils visent les mathématiques et « pas nécessairement d’autres domaines scientifiques ». OpenAI a publié son résultat mathématique directement, sans groupe désigné.
Les réserves des auteurs
L’article sur l’ETH borne lui-même sa portée : il ne permet pas de conclure que les problèmes NP en général admettent des algorithmes sous-exponentiels, écrit-il, car des bornes de ce type ne se transmettent pas par les réductions habituelles entre problèmes. La question P contre NP reste ouverte, et aucun solveur SAT n’ira plus vite grâce à ce texte : selon OpenAI, en tirer des gains pratiques « exigera d’importantes recherches supplémentaires ».
Une preuve Lean ne vaut que pour son énoncé formel. Il faut encore vérifier, avec le fichier de comparaison publié par OpenAI, que cet énoncé correspond à l’ETH de la littérature. Le 7 octobre, l’entreprise a retiré trois manuscrits après une erreur de signe et en a révisé 14 autres, et son dépôt prévient que « certains résultats non formalisés pourraient poser problème ». Aucun des trois résultats n’a été relu par des pairs.
Notre analyse
Les dates d’OpenAI montrent des preuves qui arrivent plus vite que les spécialistes ne peuvent les lire : un jour entre une réfutation rédigée en langage naturel et sa version Lean, alors que l’examen collectif en est encore à sa préparation. Ici, l’étape lente est la compréhension du résultat, et ce sont les auteurs de l’hypothèse de 1999 qui la mènent, avec Ryan Williams.
Si la réfutation tient, les théorèmes de complexité énoncés « sous l’ETH » perdent leur fondement. La lettre du groupe rappelle que les idées, les réductions et les techniques nées de décennies de recherche sur l’ETH « gardent leur valeur ».
Les prochaines étapes à suivre sont le dépôt de résultats, le blog et le formulaire annoncés par le groupe ETH, la conférence qu’OpenAI s’est engagée à financer, une éventuelle reconstruction de l’argument écrite par des humains et la rédaction, par le groupe Gross, des travaux sur Yang-Mills et la QCD. D’ici là, la réfutation de l’ETH reste, d’après les fichiers d’OpenAI eux-mêmes, un résultat revendiqué, formalisé en Lean par OpenAI, ouvert à toute vérification et pas encore relu par des pairs.
Sources
- Working with academic communities to build scientific understanding, OpenAI, 26 octobre 2026
- The Exponential Time Hypothesis is False, OpenAI, GitHub (openai/math), 25 octobre 2026
- The Exponential Time Hypothesis is False (périmètre de la formalisation Lean), OpenAI, GitHub (openai/math), 26 octobre 2026
- Local smoothing for the Euclidean wave equation, OpenAI, GitHub (openai/math), 25 octobre 2026
- Message to the TCS Community on ETH, Russell Impagliazzo, Ramamohan Paturi et Ryan Williams, 26 octobre 2026
- Podcasts about the Topic: Part II, Scott Aaronson, Shtetl-Optimized, 26 octobre 2026
- Disadvantages of Designating Mathematicians for AI Output Releases, Advisory Group on Mathematics and Artificial Intelligence, sur le blog de Terence Tao, 25 octobre 2026
- OpenAI announces three big science discoveries and a new way to work with academics, Richard Lawler, The Verge, 26 octobre 2026
Image d’en-tête : graphique MACCUS, données de l’article d’OpenAI The Exponential Time Hypothesis is False (25 octobre 2026)
