OpenAI affirme qu'un modèle d'intelligence artificielle a trouvé un moyen de réfuter l'hypothèse du temps exponentiel (ETH), une conjecture d'informatique théorique proposée en 1999. Cette affirmation n'a aucun lien avec Ethereum, la cryptomonnaie qui s'échange sous le ticker ETH, ni avec le cofondateur d'Ethereum Vitalik Buterin.

L'annonce a néanmoins suscité des plaisanteries sur Crypto Twitter. « Damn algo traders just slaughtered $ETH », a publié sur X un utilisateur nommé Takumi, tandis qu'Andrew Jiang a écrit : « Vitalik has been real quiet since this came out ».

L'ETH en question a été proposée par les informaticiens Russell Impagliazzo, Ramamohan Paturi et Francis Zane. Selon cette conjecture, le problème logique connu sous le nom de 3-SAT ne peut être résolu de manière substantiellement plus rapide qu'en examinant chaque combinaison possible de variables. Dans 3-SAT, l'objectif est de déterminer si des affectations vrai-faux peuvent satisfaire un ensemble de règles, chaque règle comportant trois variables.

Des centaines d'articles académiques se sont appuyés sur cette hypothèse pour établir que certains problèmes de théorie des graphes, de biologie computationnelle, de bases de données et de géométrie ne peuvent être résolus rapidement, selon OpenAI. La société a indiqué que réfuter ETH pourrait rouvrir la question de savoir à quel point ces tâches pourraient être accélérées et aider les chercheurs à rechercher de meilleurs algorithmes.

« La réfutation de l'ETH rouvre les questions sur la vitesse à laquelle ces tâches pourraient devenir », a écrit OpenAI dans son article de blog, « et pourrait aider à orienter la recherche de meilleurs algorithmes ».

L'article de 67 pages d'OpenAI, daté du 17 octobre et révisé le 25 octobre, décrit un algorithme déterministe — qui n'utilise pas d'aléatoire — dénombrant chaque affectation satisfaisante de ces casse-tête en temps sous-exponentiel. Cela signifie que la quantité de travail croît plus lentement que toute fonction exponentielle du nombre de variables. Comme compter le nombre de solutions est plus difficile que de déterminer s'il en existe au moins une, le résultat résout également le problème de décision.

OpenAI a déclaré que son IA avait découvert la réfutation le 16 octobre et que le résultat avait été formalisé en Lean, un logiciel qui vérifie mécaniquement chaque étape logique, le 17 octobre. L'article et la formalisation sont disponibles sur GitHub. OpenAI a précisé que cela faisait suite à la publication de 722 manuscrits mathématiques plus tôt dans le mois, dont seulement 162 comprenaient un résultat principal vérifié par ordinateur. Ce format vérifiable par machine permet aux chercheurs indépendants de vérifier par eux-mêmes chaque étape de l'argumentation.

Impagliazzo, Paturi et le professeur du MIT Ryan Williams dirigent un examen indépendant de cette affirmation. Dans une lettre ouverte, ils ont averti que leur participation ne devrait pas être interprétée comme une caution.

« Notre implication ne doit pas être considérée comme une certification de cette affirmation », ont écrit les trois chercheurs, ajoutant qu'« un résultat de cette importance nécessite un examen indépendant attentif et la compréhension que d'autres peuvent le reconstruire, le remettre en question et le développer ».

OpenAI a indiqué que les participants n'avaient signé aucun accord de confidentialité et travaillaient bénévolement. La société a également accepté de publier toutes les données brutes et de financer une conférence consacrée à ce résultat.

Les implications pratiques restent incertaines. « Trouver de tels algorithmes et transformer les avancées théoriques en améliorations pratiques nécessiteront des recherches supplémentaires importantes », a écrit OpenAI. L'article précise également que le résultat n'établit pas que chaque problème de la classe de complexité NP peut être résolu en temps sous-exponentiel.

Cela signifie que le problème P contre NP demeure ouvert. 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 non résolue est de savoir si chaque problème dont la réponse peut être vérifiée efficacement peut aussi être résolu efficacement.

Anthropic est entré dans la discussion le 26 octobre avec un article attribué à Claude et intitulé « A 2^o(n) Time Algorithm for 3-SAT ». Le dépôt, qui aborde également le problème ETH, indique qu'un modèle de recherche Claude interne a découvert l'algorithme. Il précise que « le résultat est purement asymptotique et ne dit rien sur la résolution pratique des formules ».

Claude avait formalisé le dernier théorème de Fermat en Lean en septembre. Le mathématicien Terence Tao avait averti de la possibilité de chevauchements entre efforts d'IA, écrivant en septembre : « We have now seen that even the rumor of someone working on a problem can trigger a massive amount of AI-powered effort to flatten it before the original research project has time to reach its full potential ».

La contribution récente de 5 millions de dollars d'OpenAI à la Simons Foundation financera des ateliers, des conférences et des programmes spéciaux destinés à aider les chercheurs à examiner et à développer les résultats produits avec l'IA.

Source : Decrypt