OpenAI et Anthropic affirment avoir infirmé l'hypothèse ETH sur la difficulté des problèmes
L'hypothèse ETH affirme que, pour les puzzles difficiles comme un immense sudoku, le temps de recherche de la solution croît de façon explosive avec le nombre de variables. OpenAI a déclaré que son modèle avait trouvé un algorithme plus rapide, puis, quelques heures plus tard, Anthropic a présenté sa propre réfutation. Si la vérification tient, de nombreux articles reposant sur ETH devront être révisés, mais pour l'instant il s'agit d'affirmations, pas d'une preuve acceptée. Ryan Williams, du MIT, recueille les réactions des scientifiques et demande que les preuves soient rendues publiques. OpenAI a vérifié : le nouvel algorithme n'entraîne pas la casse des cryptosystèmes. L'hypothèse ETH a été formulée en 1999 par Russell Impagliazzo et Ramamohan Paturi, de UC San Diego.
Traité par IA depuis TechCrunch ; édité par Hamidun News
Imaginez que vous développiez un service qui doit établir un planning de postes, des itinéraires de coursiers ou des versions de paquets compatibles. Ces problèmes butent souvent sur l'énumération exhaustive : plus il y a de données d'entrée, plus la recherche de la réponse devient brutalement longue. Les informaticiens débattent depuis longtemps de la possibilité de contourner ce plafond. Aujourd'hui, deux laboratoires d'IA, OpenAI et Anthropic, affirment que leurs modèles ont trouvé un moyen d'aller plus vite que ce qui était considéré comme possible. Voyons ce qu'ils ont exactement déclaré, et pourquoi il s'agit pour l'instant d'une affirmation et non d'un fait établi.
De quelle hypothèse parle-t-on et que proclament les laboratoires
L'hypothèse du temps exponentiel (ETH) a été formulée en 1999 par Russell Impagliazzo et Ramamohan Paturi, de UC San Diego. L'idée : pour une certaine classe de puzzles logiques complexes, même l'algorithme le plus rapide voit son temps de calcul croître de façon exponentielle à mesure que le nombre de variables augmente. Concrètement, dans un sudoku, chaque nouvelle case ne rajoute pas du travail, elle le double. Pendant des années, cette « barrière » a servi de référence pour déterminer les problèmes hors de portée des ordinateurs.
OpenAI a publié les solutions de trois problèmes mathématiques connus, dont l'un remet en cause l'ETH de façon inattendue. Selon OpenAI, son modèle a trouvé un algorithme qui résout ces puzzles en temps « sous-exponentiel », c'est-à-dire plus vite que ne le prévoyait l'hypothèse. Si c'est exact, l'ETH est fausse, ou, en langage scientifique, réfutée.
La suite a été révélatrice. Le mathématicien d'Anthropic Levent Alpöge a suggéré qu'OpenAI s'appuyait sur des travaux déjà existants. Quelques heures plus tard, Anthropic a publié sa propre réfutation de l'ETH. Deux laboratoires concurrents sont arrivés à une conclusion similaire, mais cela ne remplace pas une vérification par des chercheurs indépendants.
P contre NP et cryptographie : le lien
L'ETH s'inscrit dans la famille des questions « P contre NP ». Le principe : si la réponse à un problème est facile à vérifier, est-elle pour autant facile à trouver ? Un sudoku résolu se vérifie en quelques secondes, mais imaginer la solution d'un puzzle complexe prend beaucoup plus de temps. C'est sur cette asymétrie que repose le chiffrement : celui qui détient la clé déchiffre le message, tandis que casser le code sans elle demande un temps irréaliste.
La plupart des scientifiques pensent que P ≠ NP, et l'ETH était l'un des arguments en faveur de cette position. Ryan Williams, professeur au MIT et spécialiste de la complexité algorithmique, estime que chaque théoricien devrait envisager un peu plus sérieusement l'hypothèse P = NP, même si chacun a son propre degré de scepticisme. Il considère toutefois que l'algorithme d'OpenAI n'est probablement pas le meilleur possible et que ce n'est vraisemblablement pas le dernier mot.
Ryan Williams a d'abord demandé au directeur scientifique d'OpenAI, Dan Roberts, si ce résultat compromettait certains cryptosystèmes. Selon Williams, OpenAI a effectué cette vérification et est assez convaincue qu'aucun système ne peut être cassé à partir de ce résultat. Il a cependant précisé qu'un algorithme amélioré pourrait, en principe, compromettre des systèmes utilisant certaines tailles de clés. Les ingénieurs en sécurité ont donc intérêt à suivre le débat, sans céder à la panique.
Comment ces résultats sont désormais publiés et que doit faire le lecteur
Ryan Williams avait qualifié de « attaque DDoS contre les mathématiciens » la avalanche de preuves publiées par OpenAI en octobre. Cette fois, le laboratoire a organisé le processus différemment selon les domaines. Les mathématiciens ont reçu les documents sur GitHub. Les informaticiens ont créé un groupe de travail, demandé la publication ouverte des preuves et sollicité OpenAI pour financer une conférence. Les physiciens ont également formé un groupe, qui décidera lui-même de la manière de publier leur résultat.
Ryan Williams a accepté d'apporter son aide, tout en critiquant l'approche du laboratoire : pour lui, il est essentiel de faire connaître les idées à la communauté. Avec Impagliazzo et Paturi, il a publié une lettre ouverte invitant à faire part de remarques et à discuter des règles de la contribution de l'IA à la science. Selon lui, la preuve contient des parties routinières et deux ou trois fragments « d'apparence extraterrestre », ce qui impose de travailler collectivement sur ce travail.
Voici la conclusion pratique pour les développeurs et les fondateurs :
- Si la réfutation résiste à la vérification, il faudra réviser de nombreux articles de la dernière décennie qui citent l'ETH. C'est pourquoi Ryan Williams insiste sur la tenue d'une conférence.
- Pour les produits d'aujourd'hui, rien ne change : le texte ne fournit aucune donnée sur la vitesse du nouvel algorithme sur des problèmes réels, sur les coûts de calcul ou sur le fonctionnement interne des modèles.
- Le signal pour l'industrie compte davantage que les détails : les modèles les plus avancés travaillent déjà à la frontière de l'informatique théorique, et la manière de vérifier ces résultats reste à inventer.
Ryan Williams reconnaît son inquiétude pour la formation des jeunes chercheurs, mais y voit aussi un avantage. Si tout ce que les chercheurs faisaient jusqu'ici devient des « fruits à portée de main » pour l'IA, il faudra relever le niveau des questions. En attendant une confirmation indépendante, il est raisonnable de considérer ce résultat comme une affirmation retentissante, et non comme une nouvelle vérité.
- 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 quelle hypothèse parle-t-on et que proclament les laboratoires ?
L'hypothèse du temps exponentiel (ETH) a été formulée en 1999 par Russell Impagliazzo et Ramamohan Paturi, de UC San Diego. L'idée : pour une certaine classe de puzzles logiques complexes, même l'algorithme le plus rapide voit son temps de calcul croître de façon exponentielle à mesure que le nombre de variables augmente. Concrètement, dans un sudoku, chaque nouvelle case ne rajoute pas du travail, elle le double.
Que sait-on sur P contre NP et cryptographie : le lien ?
L'ETH s'inscrit dans la famille des questions « P contre NP ». Le principe : si la réponse à un problème est facile à vérifier, est-elle pour autant facile à trouver ? Un sudoku résolu se vérifie en quelques secondes, mais imaginer la solution d'un puzzle complexe prend beaucoup plus de temps. C'est sur cette asymétrie que repose le chiffrement : celui qui détient la clé déchiffre le message, tandis que casser le code sans elle demande un temps irréaliste.
Comment ces résultats sont désormais publiés et que doit faire le lecteur?
Ryan Williams avait qualifié de « attaque DDoS contre les mathématiciens » la avalanche de preuves publiées par OpenAI en octobre. Cette fois, le laboratoire a organisé le processus différemment selon les domaines. Les mathématiciens ont reçu les documents sur GitHub. Les informaticiens ont créé un groupe de travail, demandé la publication ouverte des preuves et sollicité OpenAI pour financer une conférence. Les physiciens ont également formé un groupe, qui décidera lui-même de la manière de publier leur résultat.
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.