Trois lettres ont brouillé la lecture d’une annonce scientifique : ETH. Dans le travail présenté par OpenAI, elles ne désignent pas Ethereum, mais l’« hypothèse du temps exponentiel », une conjecture sur la difficulté de certains problèmes de calcul. L’entreprise affirme que ses modèles en ont trouvé une réfutation. Ce serait un résultat théorique majeur, mais son examen ne se résume pas à lire le titre du manuscrit.
Le dossier publié en octobre 2026 permet de distinguer l’affirmation d’OpenAI, l’algorithme décrit et le travail de compréhension engagé par des chercheurs. Il permet aussi d’écarter deux conclusions trop rapides : cette annonce ne résout pas P contre NP et ne fournit pas, à elle seule, une recette pour casser les cryptomonnaies.
Un problème de règles à satisfaire
Le problème étudié consiste à attribuer des valeurs « vrai » ou « faux » à des variables, en respectant un ensemble de contraintes. Une variable peut apparaître directement ou sous sa négation. Dans le cas appelé 3-SAT, chaque clause comporte au plus trois de ces éléments ; il faut rendre toutes les clauses vraies simultanément.
Pour se représenter le nombre de possibilités, imaginons des interrupteurs à deux positions. Dix interrupteurs autorisent 1 024 configurations ; vingt en autorisent 1 048 576. Cet exemple illustre la croissance du nombre de combinaisons, pas le temps réel d’un logiciel : un algorithme peut éviter d’examiner chacune d’elles.
L’hypothèse ETH ne dit donc pas simplement qu’il faut essayer toutes les configurations. Elle pose une limite plus générale : on ne pourrait pas résoudre tous les cas de 3-SAT en un temps sous-exponentiel par rapport au nombre de variables. Améliorer la base d’une croissance exponentielle ne suffit pas à la réfuter. Il faut franchir une autre frontière dans la façon dont le temps de calcul augmente.
Cette précision change le sens de l’annonce. Il ne s’agit pas seulement d’un programme un peu plus rapide sur des exemples difficiles. Le manuscrit revendique une méthode dont la borne de complexité contredit la conjecture elle-même.
Ce que revendique le manuscrit
Dans sa version du 25 octobre, le texte de 67 pages présente un algorithme déterministe : son fonctionnement ne dépend pas de tirages aléatoires. Il vise le comptage exact des affectations qui satisfont une formule, pour des clauses de taille maximale fixée à l’avance. Cette dernière condition compte : le paramètre décrivant cette taille n’est pas laissé libre de grandir sans contrainte avec le problème.
Compter les solutions permet aussi de décider s’il en existe une. Si le nombre obtenu est nul, la formule n’est pas satisfaisable ; s’il est positif, elle l’est. C’est ce passage du comptage à la décision qui relie le résultat annoncé à ETH.
Le manuscrit annonce un temps sous-exponentiel et un usage polynomial de la mémoire. Ces qualifications décrivent la croissance des ressources lorsque la taille des entrées augmente. Elles ne donnent pas un délai en secondes pour une machine particulière. Un meilleur comportement théorique à très grande échelle peut encore s’accompagner de coûts trop élevés pour des problèmes courants.
La distinction protège contre une promesse d’usage prématurée : le document présente un résultat mathématique revendiqué, pas une application disponible dont la rapidité aurait été mesurée ici. Aucun gain pratique sur les logiciels du lecteur ne peut être déduit de son seul résumé.
Une preuve formelle ne remplace pas toute l’explication
Dans sa présentation du 26 octobre, OpenAI indique que ses modèles ont trouvé la réfutation le 16 octobre et qu’une formalisation dans Lean a suivi le 17. Lean est un assistant de preuve : il permet de représenter des énoncés et des raisonnements dans un langage vérifiable par un logiciel. L’entreprise a publié le manuscrit et les éléments formels pour examen.
Un tel dispositif ajoute une possibilité de contrôle précieuse. Il faut néanmoins comprendre quel énoncé a été formalisé, sous quelles définitions, et comment il correspond à la revendication scientifique. La vérification d’un fichier, l’interprétation du théorème et l’explication de son intérêt sont des tâches liées, mais différentes. Lire un article de présentation ne revient pas à les avoir accomplies.
L’enjeu pour le lecteur est de ne pas choisir entre confiance automatique et rejet automatique. Le bon niveau de lecture consiste à identifier le résultat annoncé et les étapes qui permettent à d’autres spécialistes de le reconstruire.
Les chercheurs distinguent examen et certification
Russell Impagliazzo, Ramamohan Paturi et Ryan Williams ont présenté une initiative d’examen et de discussion. Dans leur lettre du 26 octobre, ils précisent que leur participation ne vaut pas certification de la revendication. Ils mettent l’accent sur une compréhension que d’autres chercheurs puissent reconstituer, questionner et utiliser.
Ce cadre est particulièrement utile pour un résultat présenté comme produit par l’IA. L’origine du texte ne dispense pas de rendre la démonstration intelligible. Une avancée devient exploitable lorsque ses conditions, ses limites et les idées qui la rendent possible peuvent être expliquées au-delà de son premier dossier de publication.
Cela ne signifie pas que tous les travaux antérieurs fondés sur ETH deviennent dépourvus d’intérêt. Une implication conditionnelle peut rester correcte même si son hypothèse de départ est remise en cause. En revanche, son usage comme argument de difficulté doit être réévalué à la lumière du résultat effectivement établi.
Ni P contre NP, ni outil de piratage
Le manuscrit précise que son résultat n’implique pas un algorithme sous-exponentiel pour tous les problèmes de la classe NP. La manière dont on traduit un problème en un autre peut augmenter sa taille : une borne favorable dans une formulation ne se transfère donc pas automatiquement à toutes les autres.
Il ne démontre pas davantage que tout problème dont une solution se vérifie efficacement peut se résoudre efficacement, la question connue sous le nom de P contre NP. « Sous-exponentiel » ne veut pas dire « polynomial », et encore moins « instantané ».
L’annonce mérite ainsi d’être suivie pour sa proposition scientifique précise. Pour mesurer son apport, les prochains éléments utiles seront des explications reconstructibles de l’algorithme, une clarification de ses conséquences et, séparément, d’éventuelles méthodes utilisables en pratique. Le sigle ETH est ici le début d’une question de complexité, pas un verdict sur Ethereum.
Photographie d’illustration : discussion devant un tableau de mathématiques. Les personnes photographiées ne sont pas présentées comme les auteurs ou les examinateurs du résultat.
Crédit : Yan Krukau — Pexels, licence Pexels.
