Le 26 octobre 2026, OpenAI a annoncé que son système interne avait réfuté l’hypothèse du temps exponentiel (ETH), une conjecture sur la complexité de la satisfaisabilité des formules booléennes. C’est l’affirmation de l’entreprise, qui a aussi décrit les étapes de son travail et annoncé un examen externe. OpenAI
L’ETH sert de fondement à des résultats conditionnels sur la difficulté de calculer certains problèmes. OpenAI indique qu’elle a été utilisée dans des centaines d’articles de recherche. Si la réfutation annoncée est retenue, ces résultats pourraient devoir être réexaminés.
Ce qu’OpenAI dit avoir produit
OpenAI situe la production d’une démonstration en langage naturel au 16 octobre 2026, puis sa formalisation avec Lean au 17 octobre. L’entreprise a annoncé le 26 octobre la publication du texte et de la preuve Lean. Lean est un assistant de preuve qui permet de formaliser des démonstrations mathématiques.
OpenAI a également annoncé un groupe dirigé par Russell Impagliazzo, Ramamohan Paturi et Ryan Williams, chargé d’accompagner et d’expliquer le résultat. L’entreprise précise que ses membres participent de manière indépendante et que leurs conclusions leur appartiennent.
Une démonstration formalisée et un gain pratique sont deux étapes distinctes.
Dans un commentaire technique, E8 Holographic Framework soutient que vérifier une preuve avec Lean ne suffit pas à établir le temps d’exécution d’un algorithme sur une machine réelle. Sa critique porte notamment sur la taille en bits des nombres intermédiaires, qui pourrait peser sur le coût du calcul. Cette analyse est celle du créateur de la vidéo.
L’ETH ne résout pas P vs. NP
L’affirmation d’OpenAI porte sur l’ETH, pas sur P vs. NP. Ce problème plus large demeure non résolu, rapporte le New York Times.
Les conséquences pratiques demandent encore du travail
OpenAI indique que transformer une avancée théorique en amélioration pratique nécessiterait encore beaucoup de recherches. Son annonce ne fait état d’aucun gain de performance concret.
