Une hypothèse vieille de plusieurs décennies sur les limites de l’informatique vient peut-être de rencontrer un adversaire inattendu : l’intelligence artificielle.
Le 26 octobre, l’entreprise a annoncé que ses modèles avaient produit une démonstration contestant l’hypothèse du temps exponentiel (ETH), une hypothèse de longue date sur la difficulté à résoudre certains problèmes informatiques. Les chercheurs se sont appuyés sur l’ETH dans des centaines d’études, et ces nouveaux résultats pourraient les amener à réexaminer certaines de leurs conclusions.
Mais une avancée mathématique ne se traduit pas automatiquement par des ordinateurs plus rapides. Des chercheurs indépendants doivent encore examiner la démonstration, et la découverte d’algorithmes pratiques fondés sur ce résultat pourrait nécessiter beaucoup plus de travail.
Comment l’IA d’OpenAI a remis en cause une hypothèse fondamentale de l’informatique
Selon l’annonce d’OpenAI, ses modèles d’IA ont produit une démonstration contestant l’ETH le 16 octobre. L’entreprise a utilisé Lean, un outil de vérification des démonstrations mathématiques, pour formaliser le résultat le lendemain.
L’ETH porte sur le temps nécessaire pour résoudre certains problèmes informatiques, en particulier la satisfaisabilité booléenne, ou SAT. En termes simplifiés, elle avance qu’aucun algorithme ne peut résoudre toutes les instances du problème standard 3-SAT en temps sous-exponentiel à mesure que le nombre de variables augmente.
Cette hypothèse a aidé les chercheurs à établir des limites conditionnelles à l’efficacité avec laquelle d’autres problèmes informatiques peuvent être résolus. Si l’ETH est fausse, certaines de ces conclusions devraient être réexaminées.
OpenAI a qualifié l’ETH d’« largement considérée comme vraie ». Depuis des décennies, les chercheurs s’appuient sur elle pour étudier les limites du calcul dans des domaines comme la théorie des graphes, la biologie computationnelle et les bases de données.
OpenAI a rendu publiques les deux versions de la démonstration. Russell Impagliazzo et Ramamohan Paturi, de l’UC San Diego, ainsi que Ryan Williams, du MIT, dirigeront un groupe indépendant chargé d’examiner les résultats.
Une réfutation pourrait changer la recherche algorithmique
Si la démonstration d’OpenAI résiste à l’examen, les chercheurs devront peut-être réexaminer les études antérieures qui s’appuyaient sur l’ETH pour établir quels problèmes informatiques sont difficiles à résoudre.
Cependant, remettre en cause une hypothèse de complexité computationnelle ne signifie pas que les logiciels existants s’exécuteront soudainement plus vite ni que les problèmes complexes deviendront plus faciles à résoudre.
OpenAI a reconnu que davantage de travaux étaient nécessaires : « La découverte de tels algorithmes et la transformation des avancées théoriques en améliorations concrètes nécessiteront d’importants travaux de recherche supplémentaires. »
Interesting Engineering a également fait état de deux autres démonstrations produites par l’IA, portant sur la conjecture du lissage local et les théories des champs quantiques. Des chercheurs examinent ces résultats dans le cadre de processus d’évaluation distincts.
Ce qu’a découvert eWeek : trois tests avant que la démonstration ne transforme l’informatique
OpenAI a publié sa démonstration et présenté ses projets d’évaluation indépendante. Cependant, les chercheurs doivent encore répondre à plusieurs questions avant que ces résultats puissent conduire à des améliorations de l’informatique dans le monde réel.
Jalon de la recherche | Ce qui a été fait | Ce qui reste à faire |
| Démonstration formelle | Les versions en langage naturel et en Lean sont accessibles au public | Des chercheurs indépendants doivent examiner et interpréter la démonstration |
| Implications scientifiques | La démonstration remet en cause les hypothèses fondées sur l’ETH | Les chercheurs doivent déterminer quels résultats antérieurs doivent être réexaminés |
| Algorithmes pratiques | Aucun algorithme de production plus rapide n’a été démontré | Les chercheurs doivent concevoir et tester des algorithmes susceptibles d’améliorer les performances informatiques |
L’importance de la démonstration rapportée par OpenAI dépasse la résolution d’un problème mathématique difficile. L’ETH a façonné des décennies de recherche sur la complexité computationnelle, aidant les scientifiques à établir les limites de l’efficacité avec laquelle certains problèmes peuvent être résolus.
Si la réfutation est validée, les chercheurs devront peut-être réexaminer les résultats qui dépendent de cette hypothèse, même si ceux étayés par d’autres arguments mathématiques resteront valides.
La question la plus importante est de savoir si cette découverte pourrait à terme conduire à de meilleurs algorithmes. Réfuter l’ETH établirait que certains problèmes informatiques peuvent être résolus plus rapidement sur le plan théorique, mais cela ne produirait pas automatiquement des algorithmes adaptés aux applications du monde réel.
Transformer cette intuition mathématique en améliorations mesurables des performances pourrait nécessiter des années de recherche supplémentaires.
Ce résultat met également en lumière une difficulté de la découverte scientifique assistée par l’IA. OpenAI affirme que sa démonstration a été formalisée avec Lean, qui vérifie que les arguments mathématiques suivent des règles logiques précises.
Cependant, la vérification formelle ne remplace pas l’examen indépendant des hypothèses, de l’interprétation et des implications plus larges d’une démonstration. Les chercheurs doivent encore établir ce que ce résultat signifie pour la complexité computationnelle et s’il ouvre de nouvelles pistes réellement prometteuses pour le développement d’algorithmes
Une précédente enquête de Scientific American sur les mathématiques assistées par l’IA a montré à quel point il peut être difficile pour les mathématiciens d’interpréter des démonstrations produites par l’IA, même lorsque des vérifications formelles étayent leur exactitude.
La difficulté ne consiste pas simplement à établir si une démonstration est valide, mais à comprendre ce qui la rend efficace et comment ses enseignements pourraient orienter les recherches futures.
Ce que signifie la démonstration d’OpenAI pour les développeurs et les entreprises
Les entreprises ne devraient pas s’attendre à ce que leurs logiciels s’exécutent plus rapidement à la suite de l’annonce d’OpenAI. L’entreprise n’a pas démontré d’améliorations des performances des bases de données, des outils d’optimisation ou d’autres logiciels utilisés en production.
Pour les développeurs et les équipes de recherche, il reste davantage à étudier. Ils peuvent examiner la démonstration publiée, vérifier si leurs travaux existants reposent sur l’ETH et suivre les conclusions du groupe de recherche indépendant.
Les responsables informatiques, eux, ont peu de raisons de modifier leurs projets d’infrastructure ou leurs budgets logiciels sur la seule base de cette annonce. Toute amélioration future de l’informatique devra encore être développée, testée et comparée aux solutions existantes.
Si les chercheurs utilisent finalement la démonstration pour développer des algorithmes plus rapides, les bénéfices pourraient s’étendre aux secteurs qui dépendent de calculs complexes et de vastes jeux de données.
D’ici là, les entreprises ont intérêt à évaluer les performances informatiques en fonction de ce que leurs systèmes peuvent réellement fournir, plutôt qu’en fonction de ce que des découvertes mathématiques produites par l’IA pourraient rendre possible.
À lire également : pour en savoir plus sur la manière dont OpenAI répond aux préoccupations liées à la recherche mathématique produite par l’IA, découvrez comment son engagement de 5 millions de dollars vise à soutenir les mathématiciens et la vérification indépendante.