Une entreprise d'intelligence artificielle affirme avoir fait tomber, grâce à l'un de ses modèles, une conjecture qui structure la théorie de la complexité algorithmique depuis près de trente ans. L'information, relayée par le site chinois Science Net (科学网), est de celles qu'il faut manier avec précaution : tant que la communauté des spécialistes n'a pas examiné la démonstration, il s'agit d'une annonce, non d'un résultat établi. Mais l'enjeu est assez considérable pour mériter qu'on prenne le temps d'expliquer de quoi il retourne.
Ce que rapporte Science Net
Selon Science Net, l'entreprise américaine OpenAI affirme que l'un de ses modèles d'IA a réfuté l'hypothèse du temps exponentiel, plus connue sous son sigle anglais, ETH (pour Exponential Time Hypothesis). Le site précise que cette hypothèse a été formulée en 1999 par des chercheurs établis en Californie, et qu'elle sert de fondement à une large part de l'informatique théorique depuis près de trente ans.
À l'heure où nous écrivons, nous n'avons pas pu recouper cette annonce avec une publication scientifique, un préprint ou une communication détaillée d'OpenAI. Nous nous en tenons donc à ce que rapporte Science Net, sans ajouter de détails sur la méthode employée, l'identité des vérificateurs ou la portée exacte du résultat. Ces éléments seront déterminants, et il convient de les attendre.
L'hypothèse du temps exponentiel, expliquée simplement
Pour comprendre l'importance de la nouvelle, il faut d'abord saisir ce que dit l'ETH. La théorie de la complexité classe les problèmes selon le temps de calcul qu'exigent les meilleurs algorithmes connus. Certains problèmes se résolvent vite, même lorsque leurs données grossissent. D'autres, au contraire, voient leur difficulté exploser.
Parmi ces derniers figure le célèbre problème SAT, qui consiste à déterminer si une formule logique composée de nombreuses variables peut être rendue vraie par un choix adéquat de valeurs. Personne ne connaît d'algorithme qui le résolve, dans le pire des cas, sans que le temps de calcul augmente de façon exponentielle avec le nombre de variables. L'ETH érige cette observation en postulat : elle affirme, en substance, qu'il n'existe pas de raccourci radical pour ce type de problème, et que le temps exponentiel est un plancher que l'on ne saurait franchir.
C'est une hypothèse plus forte, et donc plus risquée, que la fameuse conjecture « P différent de NP », qui demeure l'un des grands problèmes ouverts des mathématiques. L'ETH précise de manière quantitative ce que « difficile » signifie, ce qui la rend très utile en pratique.
Pourquoi tant de résultats en dépendent
L'intérêt de l'ETH tient à sa fécondité. Depuis sa formulation, les chercheurs s'en servent comme point de départ pour démontrer des bornes inférieures conditionnelles : si l'ETH est vraie, alors tel autre problème ne peut pas être résolu plus vite qu'un certain seuil. Ces résultats forment un édifice dense, où des centaines de conclusions reposent sur le même socle.
De ce fait, remettre en cause l'ETH ne reviendrait pas à corriger un détail. Ce serait fragiliser toutes les conclusions qui s'y adossent, et obliger les spécialistes à vérifier lesquelles survivent et lesquelles doivent être reformulées. Une telle réévaluation pourrait aussi ouvrir la porte à des algorithmes plus rapides que prévu pour certaines classes de problèmes, avec des retombées possibles en optimisation, en logistique ou en conception de circuits. Il ne s'agit là que d'hypothèses de travail, nullement de conséquences annoncées.
Pourquoi il faut rester prudent
Plusieurs raisons invitent à la retenue.
D'abord, l'annonce émane de l'entreprise même qui développe le modèle. Ce n'est pas un motif de la rejeter, mais c'est une raison de demander une vérification indépendante. En mathématiques et en informatique théorique, une démonstration vaut par sa vérifiabilité : elle doit pouvoir être lue, contrôlée et reproduite par des pairs, ligne après ligne.
Ensuite, la formulation même du résultat compte. Réfuter l'ETH au sens strict exigerait d'exhiber un algorithme sous-exponentiel pour un problème comme SAT, ce qui serait une percée spectaculaire. Il existe toutefois des variantes de l'hypothèse, plus fortes ou plus faibles, et un énoncé qui en invalide une seule n'a pas la même portée. Les comptes rendus journalistiques, y compris celui de Science Net tel que nous le résumons, ne permettent pas de trancher cette question.
Enfin, l'histoire de la discipline rappelle que les annonces de preuves extraordinaires se heurtent souvent à des failles découvertes après coup. Certaines démonstrations retentissantes ont été retirées ou corrigées après des mois d'examen. La vérification formelle, qui consiste à faire contrôler la preuve par un assistant logiciel, est une voie qui s'est beaucoup développée et qui pourrait jouer un rôle ici.
Une IA qui produit des mathématiques : le vrai sujet
Au-delà du cas précis, l'annonce s'inscrit dans un mouvement plus large : l'usage de modèles d'IA non plus seulement pour résumer ou rédiger, mais pour explorer des questions de recherche fondamentale. Si la démarche était confirmée, elle illustrerait un changement de nature : la machine ne se contenterait plus d'assister le chercheur, elle contribuerait à produire des résultats originaux dans un domaine où la rigueur est la règle.
Cela soulève des questions de fond. Comment attribuer le mérite d'une découverte lorsqu'un modèle y contribue ? Comment les revues et les comités de lecture doivent-ils traiter des preuves générées ou assistées par IA ? Quelle part de confiance accorder à un raisonnement dont on ne peut pas toujours reconstituer le cheminement ? Les mathématiciens y réfléchissent déjà, et un résultat de cette ampleur accélérerait le débat.
Ce qu'il faut surveiller
Plusieurs jalons permettront de savoir si l'annonce résiste à l'examen :
- la publication d'un texte complet de la démonstration, sous forme de préprint ou d'article, accessible aux spécialistes ;
- les réactions des chercheurs en théorie de la complexité, notamment ceux qui travaillent sur les bornes inférieures conditionnelles ;
- une éventuelle vérification formelle de la preuve ;
- la précision de l'énoncé exact réfuté, et de ses conséquences pour les résultats qui dépendaient de l'ETH.
Tant que ces éléments ne sont pas réunis, la prudence s'impose. Mais si la réfutation devait être confirmée, elle compterait parmi les moments marquants de l'informatique théorique de la décennie, et marquerait une étape dans la manière dont l'intelligence artificielle s'invite dans la recherche fondamentale.