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.

Par ·

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

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

Tableau récapitulatif

Tableau récapitulatif
PointCe qui est affirmé au 7 novembre 2026Source
AnnonceDeux 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 LeanAI Weekly
Taille de basculeEnviron 10^2 389 variables (OpenAI), 10^10 000 (cas à cinq clauses d'Anthropic)AI Weekly
RelecteursImpagliazzo, Williams, Paturi ; déclaration commune : pas une certificationAI Weekly
P contre NPNon tranché, selon les deux laboratoiresLet'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

Une erreur dans cet article ? Signalez-la · Notre politique de corrections

Logo OrigoTech

Nouveau : l’application iPhone et iPad

OrigoTech est maintenant une application iPhone et iPad

Lisez les articles en natif, avec des repères « Nouveau » sur les non-lus, la recherche locale et la lecture hors ligne de ce que vous avez déjà chargé. Gratuite, sans compte, iOS 17 ou plus ; des publicités s’affichent entre les articles.

Icône de Rekha : une maison tracée d'un seul trait

Du même auteur Autopromotion

Un chemin eulérien, au doigt

Rekha, le jeu iPhone de l'auteur d'OrigoTech : relier tous les points d'un seul trait sans parcourir deux fois la même liaison, sur 500 dessins tous solubles.

La lettre OrigoTech

Un résumé sourcé de l'actualité des outils IA, chaque semaine.

À lire aussi