OpenAI a publié un article de 67 pages affirmant que l'IA de l'entreprise a réfuté l'hypothèse du temps exponentiel (ETH). Cette conjecture remonte à 1999 et n'a aucun lien avec Ethereum, le prix d'Ethereum ou son cofondateur Vitalik Buterin. Cette affirmation a suscité des discussions parmi des mathématiciens et des utilisateurs de cryptomonnaies sur X. Un utilisateur de X, Takumi, a plaisanté : « Merde, les algorithmes viennent de faire plonger $ETH ». Andrew Jiang a écrit : « Vitalik est resté très silencieux depuis la sortie de cette nouvelle. »
Les informaticiens Russell Impagliazzo, Ramamohan Paturi et Francis Zane ont proposé l'HYPOTHÈSE ETH. Cette conjecture affirme que résoudre le problème logique 3-SAT ne peut pas être beaucoup plus rapide que de tester chaque combinaison possible. Le problème 3-SAT consiste à trouver des affectations vrai-faux qui satisfont des règles impliquant trois options à la fois. OpenAI affirme que des centaines d'articles s'appuient sur l'HYPOTHÈSE ETH pour établir des limites computationnelles en théorie des graphes, en biologie computationnelle, en bases de données et en géométrie. OpenAI soutient que réfuter l'HYPOTHÈSE ETH relance les questions sur les améliorations possibles de vitesse et pourrait orienter la recherche vers de meilleurs algorithmes.
Le document porte une date du 17 octobre et une date de révision du 25 octobre. Il présente un algorithme déterministe, qui n'utilise aucune randomisation, pour compter toutes les affectations satisfaisantes en temps sous-exponentiel. Le temps sous-exponentiel signifie que le travail requis augmente plus lentement que toute fonction exponentielle du nombre de variables. Compter les affectations satisfaisantes est plus difficile que de déterminer si une affectation satisfaisante existe, donc l'algorithme de comptage résout également le problème de décision. OpenAI affirme que l'IA a découvert la réfutation revendiquée le 16 octobre. OpenAI indique que le résultat a été formalisé le 17 octobre à l'aide de Lean, un logiciel qui vérifie mécaniquement chaque étape logique. Le document et la formalisation sont disponibles sur GitHub. OpenAI a également publié 722 manuscrits mathématiques via GitHub plus tôt ce mois-ci, mais seuls 162 incluaient un résultat principal vérifié par ordinateur.
Impagliazzo, Paturi et Ryan Williams du MIT mènent un examen indépendant de la revendication. Les trois chercheurs ont averti dans une lettre ouverte que la participation ne doit pas être interprétée comme une certification. Les chercheurs ont déclaré qu'une découverte d'une telle importance nécessite un examen indépendant rigoureux et une explication que d'autres chercheurs peuvent reconstituer, remettre en question et développer. OpenAI affirme que les participants ne sont pas rémunérés et n'ont signé aucun accord de non-divulgation. OpenAI a accepté de publier toutes les données brutes et de financer une conférence sur le résultat.
OpenAI met en garde contre le fait que l'identification d'algorithmes utiles et la traduction des progrès théoriques en gains pratiques nécessiteront des recherches supplémentaires considérables. L'article ne démontre pas que tous les problèmes NP admettent des solutions en temps sous-exponentiel. P regroupe les problèmes que les ordinateurs peuvent résoudre efficacement, tandis que NP regroupe les problèmes dont les solutions proposées peuvent être vérifiées efficacement. La question P contre NP, qui demande si la vérification efficace implique toujours une solution efficace, reste sans réponse.
Anthropic a ensuite publié un article attribué à Claude, intitulé « A 2^o(n) Time Algorithm for 3-SAT » et daté du 26 octobre. Le dépôt accompagnant indique qu'une version interne de recherche de Claude a découvert l'algorithme, qui traite également l'ETH. Le dépôt précise que le résultat concerne le comportement asymptotique et ne prétend pas résoudre des formules de manière pratique. Claude a formalisé le dernier théorème de Fermat en utilisant Lean en septembre. Le mathématicien Terence Tao a averti en septembre que même les rumeurs de recherches sur un problème peuvent déclencher d'importants efforts assistés par l'IA avant que le projet original ne soit pleinement développé.
OpenAI a récemment contribué 5 millions de dollars à la Fondation Simons. Cette contribution soutiendra des ateliers, des conférences et des programmes spéciaux visant à aider les chercheurs à examiner et à étendre les résultats produits par l'IA.