Un ordinateur peut effectuer des milliards d’opérations sans parvenir à résoudre certains problèmes dans un délai raisonnable. La difficulté ne vient pas toujours de la puissance de la machine : lorsque le nombre de possibilités à examiner augmente très vite, même un ordinateur plus performant finit par être dépassé.

Mais jusqu’où cette difficulté est-elle inévitable ? Dans une annonce publiée le 26 octobre 2026, OpenAI affirme avoir réfuté une hypothèse importante sur le sujet : celle du temps exponentiel, ou ETH.

Sur X, Sébastien Bubeck, chercheur en intelligence artificielle chez OpenAI, évoque déjà « peut-être la plus grande surprise » de ses vingt années à suivre l’informatique théorique. Le résultat pourrait être majeur, mais doit encore faire l’objet d’un examen indépendant approfondi.

Cette annonce s’inscrit par ailleurs dans une série de percées revendiquées par OpenAI en mathématiques. Le 8 septembre, l’entreprise affirmait déjà avoir résolu une partie du problème de Navier-Stokes, l’un des sept « problèmes du millénaire », avant d’annoncer des progrès sur un autre de ces grands défis, sans préciser lequel à l’époque.

OpenAI a annoncé plusieurs découvertes scientifiques le 26 octobre 2026. // Source : Greg Brocklman sur X

Que dit exactement l’hypothèse du temps exponentiel ?

Imaginez des interrupteurs qui doivent respecter plusieurs règles : « au moins un de ces trois interrupteurs doit être allumé », « celui-ci doit être éteint, ou celui-là allumé, ou un troisième éteint »… La question est simple : existe-t-il une configuration qui respecte toutes les règles à la fois ? Lorsque chaque règle prend la forme de trois conditions reliées par « ou », on parle d’un problème de logique appelé 3-SAT, sur lequel porte l’hypothèse du temps exponentiel.

Avec n interrupteurs, il existe 2ⁿ configurations possibles. Tout essayer devient donc rapidement interminable. Mais les informaticiens ne sont pas obligés de procéder ainsi : des algorithmes permettent d’éliminer des possibilités sans les tester une par une.

L’hypothèse du temps exponentiel affirme que ces raccourcis ont une limite fondamentale. Même avec la meilleure méthode possible, le temps nécessaire pour résoudre les cas les plus difficiles resterait exponentiel par rapport au nombre de variables. Autrement dit, la difficulté ne viendrait pas simplement du fait que nous n’avons pas encore trouvé un algorithme assez malin : elle serait impossible à éviter.

C’est cette limite qu’OpenAI affirme avoir réfutée. Si son résultat est confirmé, cela signifierait qu’une méthode peut résoudre ces problèmes en un temps dit « sous-exponentiel », y compris dans les cas les plus difficiles. Cela ne rendrait pas tous les calculs rapides ou faciles, mais changerait ce que l’on pensait possible d’accomplir avec un algorithme.

OpenAI assure que l'hypothèse du temps exponentiel est fausse // Source : OpenAI

L’enjeu dépasse ce seul exercice de logique. En informatique, les chercheurs établissent des liens entre différents problèmes pour comparer leur difficulté. L’hypothèse du temps exponentiel sert ainsi de point de départ à de nombreux travaux : si elle est vraie, alors certains gains de vitesse sont impossibles, même avec un meilleur algorithme.

La réfuter obligerait à réexaminer ces limites. Cela n’invaliderait pas automatiquement les travaux qui s’appuient dessus, puisque leurs conclusions dépendent de cette hypothèse. Mais on ne pourrait plus invoquer l’ETH pour justifier qu’un calcul nécessite autant de temps.

L’ETH est aussi liée à P contre NP, l’un des sept problèmes du millénaire. Cette question demande, pour simplifier, si tout problème dont on peut vérifier rapidement une solution peut aussi être résolu rapidement. OpenAI ne prétend toutefois pas avoir résolu P contre NP : un algorithme « sous-exponentiel » peut encore être très lent. Dépasser la limite supposée par l’ETH ne suffit donc pas à trancher cette autre question.

Une preuve que les spécialistes doivent encore examiner

Selon OpenAI, son IA a produit la réfutation le 16 octobre 2026, avant une formalisation dans Lean le lendemain. Ce logiciel vérifie les étapes d’un raisonnement mathématique exprimé dans un langage formel. Le manuscrit et la preuve formelle sont désormais accessibles sur GitHub.

Cette vérification constitue une étape importante, mais il faut encore s’assurer que l’énoncé vérifié correspond exactement au problème que l’on prétend résoudre. Une preuve peut être logiquement correcte sans démontrer le résultat attendu, notamment si les définitions ou les hypothèses de départ ne sont pas les bonnes.

Le manuscrit et la preuve formelle sont désormais accessibles sur GitHub. // Source : Capture d’écran Numerama

L’examen sera mené par un groupe dirigé par Russell Impagliazzo et Ramamohan Paturi, de l’université de Californie à San Diego, ainsi que Ryan Williams, du MIT. Les deux premiers font partie des chercheurs à l’origine de l’hypothèse : ils vont donc étudier une démonstration qui pourrait la réfuter.

Même si la preuve est confirmée, il restera à déterminer comment l’exploiter. Un algorithme peut représenter une avancée théorique considérable tout en demandant trop de temps ou de ressources pour être utile en pratique. OpenAI reconnaît d’ailleurs que transformer ce résultat en améliorations concrètes nécessitera encore des recherches.