Analyse
OpenAI et Anthropic affirment que l'IA a réfuté l'hypothèse du temps exponentiel, mais la preuve n'est pas certifiée et le gain ne commence qu'à des tailles d'entrée astronomiques
OpenAI et Anthropic disent que l'IA a réfuté l'hypothèse du temps exponentiel. Impagliazzo parle d'une nouvelle choquante, mais la revue est en cours.
Russell Impagliazzo, qui a co-proposé l'hypothèse du temps exponentiel (ETH) dans les années 1990, a qualifié de nouvelle très choquante sa réfutation produite par IA, selon la presse relayée par AI Weekly le 7 novembre. Le cadrage demande de la prudence : deux articles, l'un d'OpenAI et l'autre d'Anthropic, annoncés le 26 octobre, revendiquent un algorithme plus rapide pour 3-SAT ; les relecteurs disent que leur participation n'est pas une certification, le résultat ne règle pas P contre NP, et le gain ne dépasse la force brute qu'à des tailles d'entrée hors de toute mémoire. Transparence : Anthropic développe Claude, qui aide à rédiger les articles de ce site, et a publié l'un des deux articles.
L'essentiel
- L'annonce : l'article d'OpenAI (67 pages) et celui d'Anthropic (49 pages) présentent des algorithmes 3-SAT en temps 2^o(n), ce qui contredirait l'ETH. Les deux disent que l'IA a beaucoup contribué et que les preuves ont été vérifiées dans Lean, selon AI Weekly.
- Ce que disait l'ETH : 3-SAT ne se résout pas en temps sous-exponentiel. C'est plus fort que P différent de NP et cela sert à montrer que de nombreux algorithmes sont presque optimaux, selon Wikipedia.
- Vérification à ce stade : un groupe composé d'Impagliazzo, de Ryan Williams et de Ramamohan Paturi a examiné le travail. Leur déclaration commune précise que leur participation ne vaut pas certification, et Williams évoque quelques parties étranges que la communauté doit étudier.
- Portée pratique : des estimations extérieures placent le point d'équilibre avec la force brute vers 10^2 389 variables pour la borne d'OpenAI et 10^10 000 pour le cas à cinq clauses d'Anthropic. Les solveurs SAT actuels et le chiffrement ne sont pas touchés.
Ce qui est montré et ce qui ne l'est pas
Un algorithme sous-exponentiel n'est pas polynomial : les deux laboratoires disent donc que le résultat ne tranche pas P contre NP, et OpenAI précise que l'accélération ne s'étend pas aux problèmes NP en général. La vérification Lean confirme la logique d'un énoncé formel, mais les relecteurs ont demandé les données brutes et une conférence, qu'OpenAI a accepté de financer, selon AI Weekly. Dates rapportées : l'IA a trouvé l'argument en langage naturel le 16 octobre, il a été formalisé le lendemain et les articles sont sortis le 26 octobre.
Puces et chiffrement : ce qui est établi
L'ETH porte sur le pire cas ; l'effet immédiat concerne donc la théorie et les bornes inférieures qui en dépendent. Parler de vérification de puces plus rapide ou de chiffrement fragilisé relève de la spéculation à long terme. BeInCrypto et Let's Data Science disent que la cryptographie actuelle et les solveurs industriels ne sont pas touchés, et AI Weekly relaie un informaticien qui juge un article de presse trompeur. HackerNoon dit que les auteurs appliquent aussi la méthode aux courbes elliptiques sur le papier ; nous n'avons pas vu cela vérifié.
Ce qui n'est pas établi
- Certification des preuves par le groupe de relecture : en attente, selon AI Weekly.
- Toute accélération utilisable sur des instances SAT réelles : non démontrée ; les seuils sont astronomiques.
- Toute attaque pratique contre le chiffrement ou les outils de conception de puces : non établie.
- Si les affirmations du Wall Street Journal et du New York Times sur les puces et le chiffrement vont au-delà de la spéculation : nous ne les avons pas lues directement.
Tableau récapitulatif
| Point | Ce qui est affirmé au 7 novembre 2026 | Source |
|---|---|---|
| Annonce | Deux articles annoncés le 26 octobre 2026 (OpenAI 67 pages, Anthropic 49 pages) | AI Weekly |
| Résultat revendiqué | 3-SAT en temps 2^o(n), vérifié dans Lean | AI Weekly |
| Taille de bascule | Environ 10^2 389 variables (OpenAI), 10^10 000 (cas à cinq clauses d'Anthropic) | AI Weekly |
| Relecteurs | Impagliazzo, Williams, Paturi ; déclaration commune : pas une certification | AI Weekly |
| P contre NP | Non tranché, selon les deux laboratoires | Let's Data Science |
FAQ
L'IA a-t-elle prouvé que P égale NP ?
Non. L'algorithme revendiqué est sous-exponentiel et non polynomial, et les deux laboratoires disent que P contre NP n'est pas tranché.
Le chiffrement est-il fragilisé ?
Pas en pratique. Les médias consultés disent que la cryptographie déployée n'est pas touchée, et le gain n'apparaît qu'à des entrées absurdement grandes.
La preuve est-elle confirmée ?
Pas encore certifiée. Les preuves ont été vérifiées dans Lean, mais les relecteurs disent que leur participation n'est pas une certification et l'étude se poursuit.
Méthode et limites
Sources vérifiées le 8 novembre 2026. Nous n'avons lu ni les deux articles, ni les fichiers Lean, ni les articles de presse d'origine ; nous nous sommes appuyés sur AI Weekly, Let's Data Science, HackerNoon, BeInCrypto et Wikipedia. Transparence : Anthropic développe Claude, qui aide à rédiger les articles de ce site. Ceci n'est pas un conseil d'investissement ni de sécurité.
Sources
- AI Weekly : OpenAI's AI Disproof of 1998 ETH Shocks Co-Author Impagliazzo (vérifié le 2026-11-08)
- Let's Data Science : OpenAI and Anthropic Broke a 1999 Conjecture. Both Found It on October 16. (vérifié le 2026-11-08)
- HackerNoon : OpenAI and Anthropic claim AI has disproved a 27-year-old computer science hypothesis (vérifié le 2026-11-08)
- BeInCrypto : OpenAI Says Its AI Refuted the Exponential Time Hypothesis. Is Bitcoin Safe? (vérifié le 2026-11-08)
- Wikipedia : Exponential time hypothesis (vérifié le 2026-11-08)
Une erreur dans cet article ? Signalez-la · Notre politique de corrections