OpenAI affirme que l’IA réfute l’hypothèse du temps exponentiel

OpenAI affirme que son IA a réfuté l’une des hypothèses les plus fondamentales de l’informatique. Il s’agit de l’Exponential Time Hypothesis, abrégée ETH, une supposition vieille de plusieurs décennies sur la difficulté croissante de certains problèmes de calcul à mesure qu’ils prennent de l’ampleur. Selon OpenAI, son IA a mis au point un algorithme plus rapide que ce que l’ETH autorise, ce qui remet en question l’hypothèse sur laquelle reposent des centaines de publications scientifiques.

En bref :

• OpenAI affirme que son IA a trouvé un algorithme qui réfute l’Exponential Time Hypothesis.
• La réfutation a été découverte le 16 octobre, vérifiée le lendemain avec le vérificateur de preuves Lean et publiée sur GitHub.
• OpenAI revendique en outre deux autres avancées en mathématiques et en physique.

Qu’est-ce que l’Exponential Time Hypothesis ?

L’ETH est une hypothèse de l’informatique théorique selon laquelle certains problèmes logiques, comme le célèbre problème 3-SAT, exigent dans le pire des cas un temps de calcul exponentiel à mesure que le nombre de variables augmente. Cette hypothèse sert de fondement à de nombreuses démonstrations et à de nombreux travaux de recherche dans le domaine de la théorie de la complexité.

OpenAI affirme que son IA a trouvé un algorithme qui fonctionne plus efficacement que ne le permet l’ETH. La découverte a été faite le 16 octobre, vérifiée un jour plus tard avec le vérificateur de preuves Lean, puis publiée sur GitHub avec sa vérification formelle.

Vérification indépendante et recherches complémentaires nécessaires

Les créateurs de l’ETH, Russell Impagliazzo et Ramamohan Paturi, examineront ces résultats avec le chercheur du MIT Ryan Williams. OpenAI indique lui-même que transposer ce résultat en algorithmes plus rapides dans la pratique exigera encore d’importants travaux de recherche complémentaires.

Outre l’ETH, OpenAI revendique deux autres avancées scientifiques. En mathématiques, son IA aurait résolu la conjecture dite de Kakeya dans toutes les dimensions, en s’appuyant sur une preuve du cas tridimensionnel publiée l’an dernier. En physique, l’entreprise affirme avoir mis au point une démonstration portant sur une partie d’un problème du prix du millénaire, une catégorie de questions mathématiques dotées d’une récompense de 1 million de dollars par solution. Ces travaux n’ont pas encore été rendus publics. Un groupe dirigé par le lauréat du prix Nobel David Gross les examinera en premier.

Les affirmations sont ambitieuses et seront examinées de façon critique par la communauté scientifique. La période à venir dira si les résultats résistent à une vérification indépendante. L’ETH est par ailleurs sans rapport avec la cryptomonnaie Ethereum, bien que celle-ci soit également abrégée ETH. Le cours d’Ethereum s’établit actuellement à 2 300 $, en baisse de 0,4 % au cours des dernières 24 heures.