Intensif Gratuit 21–22/11Intensif gratuit de 2 jours en Vibecoding (21–22 nov, 16h00 MSK) · Cohorte 3 le 23/11S'inscrire gratuitement →Cohorte 3 (23/11)

OpenAI affirme que son IA a réfuté une hypothèse de 1999 sur la vitesse de résolution des problèmes complexes

OpenAI affirme que son modèle a trouvé un algorithme pour des problèmes complexes comme le sudoku, les emplois du temps ou le problème du voyageur de commerce, qui contredit l'hypothèse du temps exponentiel (ETH) formulée en 1999. Cette hypothèse affirmait qu'avec chaque nouvelle variable, le temps de résolution dans le pire des cas double ; l'algorithme d'OpenAI, lui, croît plus lentement. La preuve, rédigée en Lean, est disponible sur GitHub et peut être vérifiée par n'importe qui. Pour l'instant, il ne s'agit que de l'affirmation de l'entreprise, et votre planificateur ne tournera pas plus vite pour autant.

Traité par IA depuis TG: @hiaimedia (Hi, AI • Новости технологий) ; édité par Hamidun News
OpenAI affirme que son IA a réfuté une hypothèse de 1999 sur la vitesse de résolution des problèmes complexes
Source : TG: @hiaimedia (Hi, AI • Новости технологий). Collage: Hamidun News.
Écouter l'article
Fiche synthèse et chiffres clés
ParamètreDonnées
Source primaireTG: @hiaimedia (Hi, AI • Новости технологий) ↗
Rédacteur en chef
Chiffre clé #1La vérification sera dirigée par Ryan Williams du MIT et par deux auteurs de l'ETH
Chiffre clé #2Des centaines de travaux sur les graphes, la biologie et les bases de données reposent sur l'ETH
Chiffre clé #3Début octobre, trois des 722 articles d'OpenAI ont été retirés à cause d'une erreur

Imaginez que vous écriviez un planificateur de équipes pour un entrepôt ou un routeur pour des livreurs. Plus il y a de commandes et de contraintes, plus le programme ralentit, jusqu'à ne plus parvenir à suivre. L'informatique se pose depuis longtemps la question : est-ce un défaut de nos algorithmes ou la limite de la tâche elle-même ? OpenAI affirme que son modèle interne a trouvé un algorithme qui réfute l'une des principales hypothèses sur ce sujet. Pour l'instant, il ne s'agit que d'une affirmation, et nous allons examiner ce qui est déjà clair et ce qui ne l'est pas.

De quoi parle le débat, et pourquoi le sudoku

L'hypothèse du temps exponentiel (ETH) a été formulée en 1999. Elle concerne une large classe de problèmes combinatoires dont la solution est facile à vérifier mais difficile à trouver. Le sudoku en est un bon exemple : vérifier qu'une grille est correctement remplie prend une minute. La résoudre rapidement est bien plus difficile, surtout lorsque la grille passe de 9×9 à 1000×1000. Cette classe englobe aussi la construction d'emplois du temps, le problème du voyageur de commerce et des milliers d'autres problèmes de logistique, de planification et d'optimisation.

Si l'on essaie toutes les possibilités une à une, le temps de calcul maximal double à chaque nouvelle variable. Par exemple, si 50 conditions demandent une heure, 51 en demandent deux, et 52 en demandent quatre. Il existe des méthodes plus astucieuses, un peu plus rapides. Mais l'ETH affirmait que, dans le pire des cas, le temps croît tout de même de façon exponentielle. Selon OpenAI, l'algorithme trouvé par son modèle croît moins vite qu'une exponentielle. C'est cette affirmation qui contredit l'hypothèse.

Comment cela sera vérifié

La preuve est rédigée en Lean et publiée sur GitHub. Lean est un système de vérification formelle : il contrôle machine chaque étape du raisonnement, sans qu'il faille faire confiance à l'auteur. Toute personne intéressée peut lancer la vérification chez elle. Le groupe d'experts sera dirigé par le professeur Ryan Williams du MIT et par deux auteurs de l'hypothèse elle-même, Russell Impagliazzo et Ramamohan Paturi. Le résultat sera donc évalué par ceux qui savent le mieux ce qui doit être réfuté.

La prudence s'explique. Début octobre, OpenAI a publié 722 articles sur des problèmes mathématiques non résolus. Moins de vingt-quatre heures plus tard, trois de ces travaux ont dû être retirés à cause d'une erreur. Une partie des mathématiciens a critiqué cette démarche. Le médaillé Fields Terence Tao a qualifié de « déchets toxiques » les preuves que les entreprises d'IA produisent en masse dans la course aux benchmarks. Sur ce fond, ce nouveau travail, accompagné d'une formalisation, paraît nettement plus sérieux, mais il faudra tout de même attendre sa confirmation.

Ce que cela change pour les praticiens

L'ETH sert de fondement à des centaines de travaux en théorie des graphes, en biologie computationnelle et en bases de données. Beaucoup d'entre eux démontrent que certains problèmes ne peuvent pas être résolus plus vite qu'un certain seuil. Si la réfutation se confirme, ces conclusions perdront leur base, et les théoriciens devront revoir une partie de leurs résultats.

Mais il ne faut pas surestimer l'effet. La réfutation de l'ETH ne fournit pas en elle-même des algorithmes rapides pour ces problèmes : il faudra les chercher séparément. Les développeurs de planificateurs, de solveurs et d'optimiseurs n'ont donc aucune raison de réécrire leur code aujourd'hui : votre recherche d'emplois du temps ne sera pas plus rapide.

Cette histoire offre deux leçons pratiques :

  • Quand une IA produit un résultat complexe, qu'il s'agisse d'une preuve ou de code, l'essentiel est de savoir si on peut le vérifier par machine. Un format comme Lean transforme « ça semble convaincant » en « c'est vérifié ».
  • La génération est devenue bon marché, mais la vérification reste coûteuse. Les trois travaux retirés en moins d'une journée montrent que le goulot d'étranglement ne sera pas le modèle, mais l'équipe qui contrôle ses conclusions.

Si Williams, Impagliazzo et Paturi trouvent un défaut dans la preuve, l'histoire se terminera par un retrait de plus. Sinon, l'IA aura pour la première fois réfuté une hypothèse sur laquelle reposent des centaines de travaux en théorie de la complexité.

Dossier

Questions clés sur cet article

Que sait-on sur De quoi parle le débat, et pourquoi le sudoku ?

L'hypothèse du temps exponentiel (ETH) a été formulée en 1999. Elle concerne une large classe de problèmes combinatoires dont la solution est facile à vérifier mais difficile à trouver. Le sudoku en est un bon exemple : vérifier qu'une grille est correctement remplie prend une minute. La résoudre rapidement est bien plus difficile, surtout lorsque la grille passe de 9×9 à 1000×1000.

Comment cela sera vérifié?

La preuve est rédigée en Lean et publiée sur GitHub. Lean est un système de vérification formelle : il contrôle machine chaque étape du raisonnement, sans qu'il faille faire confiance à l'auteur. Toute personne intéressée peut lancer la vérification chez elle. Le groupe d'experts sera dirigé par le professeur Ryan Williams du MIT et par deux auteurs de l'hypothèse elle-même, Russell Impagliazzo et Ramamohan Paturi. Le résultat sera donc évalué par ceux qui savent le mieux ce qui doit être réfuté.

Que sait-on sur Ce que cela change pour les praticiens ?

L'ETH sert de fondement à des centaines de travaux en théorie des graphes, en biologie computationnelle et en bases de données. Beaucoup d'entre eux démontrent que certains problèmes ne peuvent pas être résolus plus vite qu'un certain seuil. Si la réfutation se confirme, ces conclusions perdront leur base, et les théoriciens devront revoir une partie de leurs résultats. Mais il ne faut pas surestimer l'effet.

ZK
Zhemal Khamidun — CPO d'Alpina Digital, product manager d'AlpinaGPT. Conçoit des produits IA depuis 2019. Hamidun News est un projet personnel devenu un agrégateur en production avec plus de 6 000 lecteurs.
✦ Unified AI Workspace · Nomad

Test Frontier LLMs & Autonomous Agents in One Workspace

Run Claude Opus 5.5, GPT-6, Gemini 3.1, and DeepSeek side-by-side in Nomad AI (nomadnet.ai) — unified model routing, deep research, and multimodal workflows under one subscription.

Try Nomad AI →Launch Nomad Agent
Qu'en pensez-vous ?
Chargement des commentaires…