L’IA réfute l’hypothèse du temps exponentiel : ce que cela signifie

OpenAI et Anthropic ont chacune publié une preuve que l’hypothèse du temps exponentiel est fausse.

L’ETH est une hypothèse vieille de 27 ans en informatique théorique selon laquelle certains problèmes ne peuvent jamais être résolus beaucoup plus vite que par force brute. Désormais, les principaux laboratoires d’IA affirment que ce n’est tout simplement pas vrai.

Si les preuves tiennent, il s’agit du résultat généré par une IA le plus significatif à ce jour en informatique. Elles obligent aussi à reconsidérer littéralement des centaines d’articles de recherche qui supposaient l’ETH vraie.

Dans cet article, nous expliquons ce que signifie réellement l’hypothèse du temps exponentiel, ainsi que P vs NP, qui y est liée. Nous verrons aussi ce que les deux laboratoires affirment exactement, comment les preuves ont été vérifiées et ce qui change (ou pas) pour la cryptographie.

P vs NP en termes simples

P versus NP demande si tout problème dont la réponse est facile à vérifier est aussi facile à résoudre. C’est l’un des sept problèmes du prix du millénaire, et il reste ouvert après cette annonce.

Le Sudoku en est l’illustration classique. Vérifier une grille remplie prend quelques secondes : on parcourt chaque ligne, colonne et bloc pour détecter les répétitions. Trouver la solution à partir d’une grille quasi vide peut prendre bien plus longtemps, et l’écart explose avec la taille de la grille.

• P est la classe des problèmes qu’un ordinateur peut résoudre en temps polynomial, c’est‑à‑dire avec un travail qui croît comme n², n³, etc., à mesure que la taille d’entrée n augmente.
• NP est la classe des problèmes dont un ordinateur peut vérifier les solutions proposées en temps polynomial.

Tout problème dans P est aussi dans NP. La question ouverte est de savoir si la réciproque est vraie. La plupart des informaticiens pensent que P ≠ NP, donc que certains problèmes sont fondamentalement plus difficiles à résoudre qu’à vérifier. La cryptographie moderne repose sur cette croyance : chiffrer est facile, mais déchiffrer sans la clé devrait être difficile.

Qu’est‑ce que l’hypothèse du temps exponentiel ?

L’ETH est plus précise : elle affirme qu’un problème NP spécifique, 3‑SAT, nécessite un temps exponentiel quels que soient l’algorithme et son ingéniosité. Russell Impagliazzo et Ramamohan Paturi de l’UC San Diego l’ont proposée à la fin des années 1990, avec des travaux fondamentaux auxquels Francis Zane a contribué.

Le problème 3‑SAT

Dans 3‑SAT, on vous donne une formule composée de n variables booléennes et d’une liste de clauses. Chaque clause relie trois conditions par OU, par exemple « x₁ est vrai OU x₄ est faux OU x₇ est vrai ». La tâche consiste à trouver une affectation des variables qui satisfait toutes les clauses simultanément.

La force brute essaie toutes les 2ⁿ affectations ; chaque variable supplémentaire double donc le travail. Vers 100 variables, c’est manifestement hors de portée.

Ce que dit l’ETH

L’ETH énonce qu’il existe une constante c > 1 telle qu’aucun algorithme ne résout 3‑SAT plus vite que cⁿ. Des algorithmes astucieux peuvent réduire la base en dessous de 2, mais jamais jusqu’à un temps sous‑exponentiel. Formellement : il existe δ > 0 tel que 3‑SAT ne peut pas être résolu en temps O(2^δn).

Pendant des décennies, les progrès ont correspondu à ce tableau. Les chercheurs ont continué à rogner la base, mais elle est restée bien au‑dessus de 1. Comme 3‑SAT peut se convertir en de nombreux autres problèmes, l’ETH est devenue une hypothèse de travail de référence. Les chercheurs l’ont utilisée pour argumenter que des problèmes comme Clique, Vertex Cover, Independent Set, et d’autres ne peuvent pas non plus être résolus beaucoup plus vite. 

Comment se compare le nouveau résultat

La nouvelle borne s’écrit en abrégé 2^o(n). Le coût par variable ajoutée se rapproche de 1 à mesure que n grandit, ce que l’ETH jugeait précisément impossible.

Ce qu’ont annoncé OpenAI et Anthropic

Les deux laboratoires ont atteint essentiellement la même borne sous‑exponentielle de manière indépendante, et tous deux ont étayé leurs articles par des preuves vérifiées par machine dans l’assistant de preuve Lean.

Anthropic indique que Claude a trouvé l’algorithme central sans intervention humaine après environ 14 millions de tokens produits. Sa méthode utilise des réseaux de tenseurs et des arguments de rang. Des chercheurs ont ensuite aidé à finaliser l’article.

Pourquoi les deux labos l’ont‑ils trouvé le même jour ?

Aucun des deux laboratoires n’a expliqué le calendrier. L’article d’Anthropic qualifie les deux résultats d’indépendants et simultanés, et les deux exposés empruntent des voies mathématiques différentes pour aboutir à une borne essentiellement identique. 

Certains éléments de contexte rendent ce chevauchement moins surprenant qu’il n’y paraît. Les deux laboratoires orientent leurs modèles vers de longues listes de problèmes ouverts, et OpenAI à elle seule a publié des centaines de manuscrits de mathématiques générés par IA début octobre. L’ETH est l’une des cibles les plus connues du domaine, et les deux modèles ont appris des mêmes recherches publiées. Les découvertes indépendantes et simultanées sont aussi un vieux motif en science, comme Newton et Leibniz pour le calcul différentiel ou Darwin et Wallace pour la sélection naturelle.

Dans quelle mesure les preuves sont‑elles solides ?

Lean confirme qu’une affirmation formelle découle logiquement de ses axiomes. Il ne peut pas confirmer que l’énoncé formel dit la même chose que l’article. Anthropic souligne qu’aucune machine ne vérifie cette correspondance, et OpenAI indique que son fichier Lean prouve une borne légèrement plus faible que son titre.

À présent, les mêmes chercheurs qui ont proposé le problème, Impagliazzo et Paturi, ainsi que Ryan Williams du MIT, organisent des ateliers pour évaluer si les énoncés formels capturent réellement l’ETH. Leur lettre insiste sur le fait que participer à la relecture n’est pas une approbation. À l’heure où nous écrivons, personne n’a publiquement trouvé de faille. 

Williams a déclaré que certaines parties de la preuve d’OpenAI semblent routinières, tandis que « deux ou trois parties d’apparence étrangère » nécessitent encore un examen attentif. Impagliazzo, l’un des auteurs de l’ETH, a qualifié le résultat de profondément surprenant.

Ce qui change et ce qui ne change pas

En pratique, presque rien ne change aujourd’hui (ouf) : les nouveaux algorithmes ne battent la force brute que sur des entrées bien plus grandes que tout ce qu’un ordinateur pourrait jamais contenir.

Pas de solveurs SAT plus rapides

L’article d’Anthropic précise que sa méthode ne dépasse la force brute que pour des entrées astronomiques. Pour des formules typiques avec cinq clauses par variable, le point de bascule est un nombre d’environ 10 000 chiffres. Dans le cas le plus général, c’est un nombre d’environ 100 millions de chiffres. 

Les auteurs ajoutent que leur approche a peu de chances d’aider en deçà d’environ 10 millions de variables. Les solveurs SAT utilisés en vérification de circuits, planification et ordonnancement ne seront pas accélérés par ce résultat.

La cryptographie n’est pas cassée

Le résultat ne touche pas à P vs NP. Personne ne le prétend. OpenAI indique avoir vérifié si l’algorithme brise des cryptosystèmes réels et se dit assez confiante que non. 

La théorie se réécrit

L’impact le plus fort concerne la recherche. Les résultats de dureté fondés sur l’ETH ou la SETH doivent désormais trouver un nouvel appui, et certains chercheurs estiment que des années de leurs travaux devront être réexaminées. Tout ne s’effondre pas pour autant. Anthropic note que le résultat ne réfute pas le problème des vecteurs orthogonaux, qui sous‑tend de nombreux résultats en complexité fine. 

Pourquoi cela compte pour l’IA

Le fait marquant tient moins à 3‑SAT qu’à l’identité des découvreurs : deux systèmes d’IA ont indépendamment renversé une conjecture à laquelle les experts humains faisaient confiance depuis une génération.

L’IA comme partenaire de recherche

Les chercheurs décrivent désormais de nouveaux résultats d’IA qui tombent toutes les une à deux semaines, perturbant des projets en cours. Des outils formels comme Lean deviennent centraux car ils permettent aux humains de faire confiance à une longue preuve écrite par machine sans en refaire chaque ligne.

Raccourcis cachés et auto‑amélioration

L’ETH cristallisait la croyance que certains problèmes de recherche n’ont pas de raccourci astucieux. Si cette croyance est fausse, d’autres problèmes évidemment difficiles pourraient aussi cacher des raccourcis.

Je pense à la découverte d’algorithmes comme un domaine où ces raccourcis pourraient beaucoup compter pour l’auto‑amélioration récursive, l’idée de systèmes d’IA qui aident à concevoir de meilleures IA. Utiliser l’IA pour trouver des algorithmes plus rapides est une piste concrète en ce sens, même si rien dans ce résultat ne le fait directement aujourd’hui.

Ce que cela signifie pour les professionnels de la donnée

Pour celles et ceux qui construisent avec les données, trois enseignements se dégagent :

• La théorie de la complexité n’est pas que académique : savoir qu’un problème est NP‑difficile vous indique quand penser heuristiques, approximations ou solveurs plutôt que recherche exacte.
• La vérification est une compétence : à mesure que l’IA génère davantage de code et d’analyses, vérifier sa production (par des tests, des preuves ou des pipelines reproductibles) compte autant que la produire.
• Les asymptotiques peuvent tromper : un algorithme « plus rapide » en théorie peut être inutile aux tailles du monde réel. 

Conclusion

Si les preuves passent l’examen des experts, l’hypothèse du temps exponentiel rejoindra la courte liste de conjectures largement admises qui se sont révélées fausses (comme la conjecture de la somme de puissances d’Euler). Mais P vs NP reste ouverte et la cryptographie est sûre pour l’instant.

Les prochains jalons à suivre sont les ateliers de relecture menés par les auteurs initiaux de l’ETH, des réimplémentations indépendantes des algorithmes, et la question de savoir si quelqu’un resserre encore la borne.

Pour acquérir les bases derrière des histoires comme celle‑ci, explorez nos cours sur les structures de données et algorithmes, la programmation Python et le machine learning. Ils couvrent la pensée Big‑O qui rend ce type de résultat lisible.