OpenAI et Anthropic affirment avoir fait tomber une hypothèse majeure de l’informatique

Le 26 octobre, OpenAI a annoncé qu’un de ses modèles avait réfuté l’« hypothèse du temps exponentiel », un pilier de l’informatique théorique formulé au tournant des années 2000. Quelques heures plus tard, Anthropic publiait sa propre réfutation, signée « Claude (Anthropic) ». Deux laboratoires, une même cible, deux preuves vérifiées par ordinateur : les théoriciens ont aussitôt sorti leurs crayons.

Des interrupteurs et une explosion

Imaginez une rangée d’interrupteurs et une liste de règles du type « au moins un de ces trois-là doit être allumé ». Existe-t-il une position de tous les interrupteurs qui respecte toutes les règles ? C’est le problème 3-SAT, star des cours d’algorithmique. Avec n interrupteurs, il y a 2ⁿ positions possibles : 100 interrupteurs, et l’on dépasse déjà mille milliards de milliards de milliards de cas.

Des algorithmes malins évitent de tout essayer. Mais l’hypothèse du temps exponentiel, proposée par Russell Impagliazzo et Ramamohan Paturi, affirme que ces raccourcis ont une limite : dans le pire des cas, le temps de calcul resterait exponentiel, de la forme 2 puissance une fraction fixe de n. De nombreux résultats s’appuient sur elle pour dire « on ne pourra pas faire beaucoup mieux ».

Ce que disent les deux preuves

La prépublication d’OpenAI, intitulée sans détour « The Exponential Time Hypothesis is False », décrit un algorithme qui compte toutes les solutions d’une formule en un temps sous-exponentiel : il croît moins vite que n’importe quel 2 puissance une fraction fixe de n. Celle d’Anthropic, « A 2^o(n) Time Algorithm for 3-SAT », arrive au même type de résultat par une autre route. Selon R&D World, un modèle de recherche interne de Claude a trouvé l’idée centrale seul, le 16 octobre, date que donne aussi OpenAI.

Gagner contre l’exponentielle ne veut pas dire aller vite. Un ordre de grandeur, en ignorant les termes cachés des formules : pour 1 000 interrupteurs, on passerait de 2¹⁰⁰⁰ étapes à environ 2³⁸⁰. Un nombre à 115 chiffres au lieu de 302. Anthropic le dit lui-même : le résultat est « purement asymptotique » et ne dit rien de la résolution de formules en pratique.

Lean, le relecteur qui ne dort jamais

La nouveauté tient aussi à la forme. Les deux laboratoires accompagnent leurs articles d’une version écrite pour Lean, un logiciel qui vérifie chaque étape d’une démonstration. Le dépôt d’Anthropic détaille la recette : environ huit minutes de calcul sur 24 processeurs virtuels, et la preuve ne s’appuie que sur les trois axiomes standards de Lean.

Mais la machine ne vérifie que ce qu’on lui donne. « Lean vérifie les preuves, mais aucune machine ne vérifie que ce fichier dit ce que dit l’article », prévient le dépôt d’Anthropic, qui garde volontairement l’énoncé court pour qu’un humain puisse le relire. Le dernier mot reste aux mathématiciens.

Les pères de l’hypothèse sortent la loupe

Ils sont justement aux premières loges. Russell Impagliazzo et Ramamohan Paturi, de l’université de Californie à San Diego, et Ryan Williams, du MIT, ont écrit à leur communauté : « Si l’affirmation est correcte, elle changera une partie importante de l’informatique théorique. » Avant d’ajouter, toujours selon R&D World : « Notre implication ne doit pas être prise comme une certification. »

La prudence s’impose d’autant plus qu’OpenAI a annoncé le même jour d’autres percées, en mathématiques et en physique, dont les éléments de physique n’ont pas été publiés. Chez OpenAI, le chercheur Sébastien Bubeck parle déjà de « peut-être la plus grande surprise » de ses vingt années à suivre le domaine, rapporte Numerama.

Pas de quoi casser vos mots de passe

Si elle tient, la réfutation ne règle pas la grande question « P contre NP », qui demande si ces problèmes ont des solutions vraiment rapides : elle montre seulement que l’exponentielle pure n’est pas une fatalité. Anthropic précise que son résultat n’apporte aucune accélération pratique. Ce n’est pas la première fois cette semaine qu’une IA bouscule les spécialistes (on en a parlé : une IA d’Anthropic qui exhume une faille dans Linux), mais cette fois, le terrain de jeu est le tableau noir.

En bref

• OpenAI, puis Anthropic quelques heures après, affirment le 26 octobre 2026 avoir réfuté l’hypothèse du temps exponentiel.
• Leurs algorithmes résoudraient 3-SAT en temps sous-exponentiel, ce qui reste astronomique en pratique.
• Les preuves sont vérifiées par le logiciel Lean, mais des humains doivent confirmer que l’énoncé vérifié est le bon.
• Les auteurs de l’hypothèse examinent le résultat et refusent, pour l’instant, de le certifier.

Sources : OpenAI, prépublication, OpenAI, annonce du 26 octobre 2026, Anthropic, article et preuve Lean, R&D World, Numerama, Wikipédia, hypothèse du temps exponentiel.

Le Bien Heureux · Rédaction Capibara · Lundi 2 novembre 2026