OpenAI a publié un article de mathématiques dont le titre affirme que l'Exponential Time Hypothesis est fausse. Si la preuve tient, elle fait tomber l'une des hypothèses de travail de l'informatique théorique moderne : que les casse-tête logiques les plus durs d'un type standard ne peuvent pas être résolus beaucoup plus vite qu'en essayant toutes les possibilités. Un très grand nombre de résultats de difficulté publiés reposent sur cette hypothèse, si bien qu'une réfutation confirmée imposerait de repenser tout le domaine.
L'article, daté du 17 octobre et révisé le 25 octobre 2026, figure dans le dépôt public de mathématiques d'OpenAI sur GitHub et n'est attribué qu'à OpenAI, sans auteur individuel. Le dépôt indique que ses manuscrits ont été produits par un modèle interne d'OpenAI non nommé et qu'il faut les considérer comme des données de recherche brutes plutôt que comme des articles aboutis. Sur plus de 60 pages, son théorème principal donne un algorithme déterministe qui compte toutes les affectations satisfaisant une formule k-CNF, c'est-à-dire une formule logique faite de clauses d'au plus k termes, pour tout k fixe supérieur ou égal à 2. Le temps d'exécution croît à peu près comme 2 puissance n divisé par la racine carrée de log n, où n est le nombre de variables, et la mémoire utilisée reste polynomiale. C'est plus lent qu'un temps polynomial mais plus rapide que tout 2 puissance une constante fois n, ce que l'hypothèse exclut précisément. Compter les solutions est plus difficile que décider s'il en existe une, donc le résultat réfute aussi la version de comptage de l'hypothèse et, selon l'article, ses variantes plus fortes.
La méthode est algébrique. D'après notre lecture de l'introduction, elle répartit les variables en groupes, traduit la formule en équations polynomiales de bas degré et compte leurs zéros communs par interpolation et sommation rapide, en s'appuyant sur des techniques antérieures de type split-and-list et d'inclusion-exclusion. L'article en tire des conséquences : comptage exact sous-exponentiel des colorations de graphes, des ensembles indépendants et des couplages parfaits, ainsi que des schémas d'approximation pour Max-k-SAT. Il précise avec soin que cela ne donne pas d'algorithmes rapides pour tous les problèmes NP, car des bornes de temps de cette forme ne se transmettent pas par les réductions ordinaires.
Le contexte impose la prudence. Les meilleurs algorithmes de comptage exact antérieurs pour 3-SAT restaient nettement exponentiels, et des décennies de travaux, dont l'algorithme PPSZ et ses raffinements, n'ont fait baisser la base de l'exposant que lentement. L'un des corollaires de l'article repose en outre sur un autre preprint d'OpenAI, The Unique Games Theorem, de septembre, lui-même non évalué.
Rien de tout cela n'a été évalué par des pairs, le dépôt d'OpenAI prévient lui-même que les résultats sans preuve formelle en Lean pourraient contenir des erreurs, et nous n'avons pas vu de réponses publiées de spécialistes de la complexité. Des résultats de cette ampleur ont déjà été annoncés puis retirés, souvent à cause d'une faille apparue seulement lorsque les spécialistes ont repris chaque lemme. L'attitude juste, pour l'instant, est l'intérêt sans adhésion : l'article est assez détaillé pour que les spécialistes le vérifient pas à pas, et leur verdict tranchera la question plus vite que n'importe quel commentaire.