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
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é.
- 21 nov. 2026OpenAI GPT-6 Cyber a trouvé une trentaine de failles dans les iPhone, Mac et autres appareils Apple
- 21 nov. 202622 agents Claude ont cherché pendant six semaines des réponses sur les trous noirs — et ont résolu deux problèmes
- 21 nov. 2026Google sépare le stockage des conversations et l'entraînement de Gemini : refuser sans perdre l'historique
- 21 nov. 2026Apple : la macOS 27.3 bêta 2 permettra de restreindre l'accès des agents IA aux fichiers du Mac
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.
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.
L'essentiel de l'IA — une fois par semaine
Sept actus qui ont vraiment compté, choisies à la main. Sans bruit ni communiqués.
C'est fait ! Vérifiez votre boîte mail pour la confirmation.