Contexte et portée des résultats publiés

Hier, OpenAI a annoncé la diffusion de 372 résultats scientifiques issus de son système d’intelligence artificielle. Parmi ces travaux figure une prétendue preuve du Unique Games Conjecture (UGC), conjecture formulée par Subhash Khot et centrale en théorie de l’optimisation. La preuve est accompagnée d’un certificat Lean, c’est‑à‑dire d’une vérification formelle dans le langage de preuve Lean, similaire à d’autres résultats de la même vague. Aucun humain n’a encore déclaré avoir compris le raisonnement sous‑jacent, ce qui place la communauté dans une phase d’interprétation assistée par IA.

Outre l’UGC, la même diffusion comprend des avancées telles que L=BPL (équivalence entre logspace probabiliste et déterministe), une multiplication d’entiers en temps O(n log 0.999… n), et une multiplication matricielle en O(n^{9/4}). Chaque résultat est présenté avec des preuves formelles partielles, mais la lisibilité humaine reste très limitée.

Preuve de l'Unique Games Conjecture générée par IA

Le document IA décrit une construction de code « bizarre » combinant un test de bruit inédit, ni long code ni short code, mais une structure récursive qualifiée d’« alien craziness ». Le texte indique que le gadget de bruit possède des propriétés de complétude et de soundness qui, selon le système, suffisent à établir la NP‑hardness optimale d’approximation pour des problèmes comme Max‑Cut et les CSP généraux, contournant ainsi le besoin de l’UGC traditionnel. La preuve repose sur un certificat Lean qui encode les étapes de vérification, mais le texte source reste obscur, avec de nombreuses références hors‑contexte et des citations jugées « irrélevantes » par les auteurs humains.

Cette situation met en évidence deux contraintes majeures : d’une part, la capacité de l’IA à générer des chaînes logiques complexes dépasse la capacité de lecture humaine ; d’autre part, l’absence de commentaires explicatifs empêche la validation indépendante sans recours à l’assistant IA. Le risque est que des erreurs subtiles subsistent dans le code de preuve, car la vérification formelle ne garantit pas l’interprétabilité.

Autres avancées majeures et limites techniques

Parmi les autres contributions, la preuve L=BPL confirme une hypothèse de dérandomisation proche de P=BPP, mais le résultat ne fournit pas de transformation explicite de machines probabilistes en machines déterministes. La multiplication d’entiers en O(n log 0.999… n) améliore le facteur constant du terme logarithmique, sans toutefois changer la classe de complexité asymptotique. La multiplication matricielle O(n^{9/4}) représente un exposant rationnel inédit, obtenu via une technique distincte de celle qui a conduit à O(n^{2.373}), mais la mise en œuvre pratique reste à évaluer.

Des séparations de complexité, comme la quasi‑quartique entre requêtes aléatoires et quantiques, ou la séparation superquadratique entre sensibilité et sensibilité de bloc, sont annoncées avec des preuves formelles partielles. De même, le lower bound Ω(n^3) sur la complexité déterminantielle du permanent dépasse le précédent borné quadratique, mais la démonstration repose sur des constructions algébriques complexes qui n’ont pas encore été décryptées.

Enjeux pour la recherche mathématique

Ces publications illustrent une transition où les IA peuvent produire des preuves formellement vérifiables sans explication humaine. Le principal défi consiste à développer des outils d’interprétation qui traduisent les certificats formels en arguments compréhensibles, afin d’éviter la dépendance à une « boîte noire ». En parallèle, la communauté doit établir des protocoles de revue qui intègrent à la fois la vérification automatique et l’évaluation conceptuelle, afin de garantir la robustesse des avancées annoncées.