L'IA invalide 27 ans de recherche en informatique
Original : An AI Breakthrough Has Made Decades of Computer Science Research ‘Irrelevant’
Pourquoi c'est important
L'ETH structurait la conception d'algorithmes depuis près de trois décennies.
OpenAI et Anthropic affirment avoir réfuté l'hypothèse du temps exponentiel (ETH), un pilier de 27 ans en informatique théorique. Des dizaines de chercheurs voient leurs travaux publiés rendus obsolètes du jour au lendemain.
OpenAI et Anthropic ont publié cette semaine des preuves — en langage naturel et en format Lean vérifiable par machine — réfutant l'hypothèse du temps exponentiel (ETH). Cette hypothèse, vieille de 27 ans, postule que la résolution de certains problèmes nécessite un effort croissant de façon exponentielle avec leur taille. Des pans entiers de la recherche en complexité algorithmique reposaient dessus.
L'impact est immédiat. Peter Jonsson, professeur à l'université de Linköping, verra son travail présenté dans deux semaines à l'IEEE Symposium on Foundations of Computer Science — mais une grande partie est désormais « morte », dit-il. Daniel Lokshtanov, de UC Santa Barbara, estime que la confirmation du résultat le rendrait « galactiquement dans l'erreur » et invaliderait une cinquantaine de ses articles. Thore Husfeldt, directeur du groupe de recherche en algorithmes à l'IT University of Copenhagen, parle d'un « résultat d'une génération » et se dit comme un « lapin surexcité » face aux nouvelles pistes à explorer.
Les preuves n'ont pas encore été vérifiées indépendamment. OpenAI sollicite des volontaires via un formulaire Google et s'engage à financer une conférence dédiée pour coordonner l'examen communautaire.