/// Signal

L’IA revendique d’avoir réfuté une hypothèse vieille de 27 ans, sans vérification indépendante

Le fait : OpenAI et Anthropic ont annoncé, la semaine du 26 octobre, que des modèles internes auraient réfuté l’hypothèse du temps exponentiel (ETH), sur laquelle reposent des centaines de travaux en complexité algorithmique. Les deux entreprises ont publié un article et une preuve formalisée en Lean sur GitHub. Aucune vérification indépendante n’a encore eu lieu.

L’hypothèse, que WIRED date de 27 ans et que The Next Web attribue à Russell Impagliazzo, Ramamohan Paturi et Francis Zane, postule que certains problèmes ne peuvent pas être résolus beaucoup plus vite qu’en temps exponentiel. La réfuter suppose d’exhiber l’algorithme qui fait mieux. Le dépôt GitHub d’Anthropic, anthropics/formal-math, contient un dossier « eth » dont le texte d’ouverture annonce un algorithme déterministe résolvant 3-SAT en 2^o(n), « which refutes the Exponential Time Hypothesis ». Côté OpenAI, l’article fait une soixantaine de pages ; les deux entreprises ont aussi publié une formalisation en Lean, un assistant de preuve qui fait vérifier les démonstrations par la machine.

Trois dates, trois étapes. Selon OpenAI, le modèle a trouvé la réfutation le 16 octobre et l’a formalisée en Lean le lendemain ; l’annonce publique date du lundi 26 octobre. Trois chercheurs ont été sollicités pour organiser un examen indépendant : Russell Impagliazzo et Ramamohan Paturi, de l’UC San Diego, qui avaient proposé l’hypothèse, et Ryan Williams, du MIT — l’universitaire que WIRED décrit comme ayant réfuté une version de l’ETH. WIRED place les deux premiers à l’UC Santa Barbara ; The Next Web, eWeek et Interesting Engineering les situent à San Diego. Dans une lettre ouverte, les trois préviennent : « Our involvement should not be taken as certification of the claim. »

L’onde de choc, elle, est déjà là. Peter Jonsson, professeur à l’université de Linköping, verra son travail présenté dans deux semaines à la conférence FOCS, par l’un de ses coauteurs ; il imagine ses collègues ouvrir leurs exposés par « ETH is false, half of my paper does not work ». L’article déposé sur arXiv le 11 avril 2026 — c’est lui que WIRED met derrière les mots « his work » — énonce d’ailleurs ses bornes inférieures « under the ETH ». Daniel Lokshtanov, professeur à l’UC Santa Barbara, estime que le résultat, s’il est confirmé, le rendra « galactically wrong » et environ 50 de ses publications « pointless » ou à réviser. Thore Husfeldt, responsable du groupe de recherche en algorithmes à l’IT University de Copenhague, résume : « As far as I can tell, it’s now all irrelevant. »

Deux réserves, et elles viennent des documents eux-mêmes. Le dépôt d’Anthropic prévient que « the result is purely asymptotic and says nothing about solving formulas in practice » : le résultat ne dit rien de la résolution pratique des formules. Le même dépôt porte la mention « Research artifact. Not maintained and not accepting contributions. » Et rien n’a encore été revu par les pairs : les chercheurs n’ont pas eu le temps de comprendre les preuves, seulement de les recevoir.