OpenAI affirme qu'un modèle d'IA a réfuté l'hypothèse du temps exponentiel (ETH), remettant en question une hypothèse sur laquelle les chercheurs s'appuyaient depuis 27 ans. Le modèle a développé un algorithme plus rapide pour le problème logique 3-SAT. Le système d'OpenAI a généré une preuve en langage naturel le 16 octobre. L'équipe a traduit la preuve en Lean le jour suivant, permettant à un logiciel de vérifier chaque étape logique.
L'algorithme publié nécessite environ 2^(n/√log n) étapes pour une entrée contenant n variables. Ce temps d'exécution contredit la borne inférieure exponentielle prédite par l'ETH, mais reste trop lent pour des applications pratiques. OpenAI souligne qu'une recherche supplémentaire substantielle est nécessaire pour obtenir des améliorations de vitesse pratiques. Russell Impagliazzo et Ramamohan Paturi de l'UC San Diego dirigeront l'analyse avec Ryan Williams du MIT. OpenAI ne revendique pas de crédit scientifique pour cette découverte, suite à un différend antérieur concernant les équations de Navier-Stokes.
Impagliazzo et Paturi ont introduit ETH en 1999. L'hypothèse concerne le 3-SAT, qui demande s'il est possible d'attribuer des valeurs vrai-ou-faux aux variables tout en satisfaisant chaque condition liée. Une solution proposée est facile à vérifier, mais chaque variable supplémentaire double le nombre de combinaisons possibles à explorer. ETH affirme qu'aucun algorithme ne peut éviter une croissance exponentielle dans le pire des cas. OpenAI indique que des centaines d'articles ont utilisé cette hypothèse pour établir la difficulté computationnelle en théorie des graphes, en biologie computationnelle et en bases de données. L'acronyme ETH n'a aucun lien avec le ticker d'Ethereum.
Le résultat ne démontre pas que P égale NP. La question P contre NP demande si tous les problèmes dont les solutions peuvent être vérifiées rapidement peuvent également être résolus rapidement. ETH a formulé une affirmation plus forte que P ≠ NP, donc réfuter ETH ne résout pas cette question plus large. Greg Brockman, président et cofondateur d'OpenAI, a souligné cette distinction quelques heures après l'annonce. L'algorithme ne menace pas directement la cryptographie protégeant le bitcoin ou l'ethereum. Les signatures bitcoin utilisent la cryptographie à courbe elliptique, et l'algorithme ne résout pas le problème mathématique sur lequel repose ce système.
Scott Aaronson, professeur d'informatique à l'Université du Texas à Austin, a déclaré que des étudiants lui avaient rapporté la prétendue réfutation. Des avancées mathématiques antérieures avaient également contredit des hypothèses sur les limites computationnelles. Anatoly Karatsuba a réfuté la conjecture de multiplication d'Andrey Kolmogorov en environ une semaine en 1960. Volker Strassen cherchait à établir l'optimalité de la multiplication matricielle standard en 1969, mais a plutôt découvert une approche plus rapide. Les machines génèrent désormais des preuves que les humains s'efforcent ensuite de comprendre. La même publication affirmait également l'existence de preuves supplémentaires impliquant l'analyse harmonique et la physique des particules.
Le cryptographe Matthew Green a averti que l'IA pourrait affaiblir les mathématiques protégeant les wallets. Benjamin Cowen, membre du Conseil d'experts en intelligence marché de BeInCrypto, a soutenu que les évolutions dans des disciplines éloignées de la finance peuvent finalement modifier les marchés. Les progrès de l'IA testent de plus en plus les hypothèses de difficulté computationnelle sur lesquelles reposent les actifs numériques.