Hypothèse du temps exponentiel (ETH)

Certains problèmes, nous ne savons les résoudre qu’en essayant presque toutes les possibilités. L’hypothèse du temps exponentiel, en anglais Exponential Time Hypothesis et en abrégé ETH, est le pari des informaticiens que, pour un problème bien précis, on ne pourra pas faire autrement, aussi malins que nous soyons. Il existe des méthodes plus rapides, mais même les meilleures auront besoin d’un nombre d’étapes qui croît exponentiellement avec la taille du problème.

L’ETH est étroitement liée au problème P versus NP, auquel nous consacrons un article à part. Si tu ne l’as pas lu, jette d’abord un œil là-bas, car nous allons nous appuyer dessus. Surtout sur ce qu’est la complexité d’un algorithme et sur la raison pour laquelle il y a un tel fossé entre n² et 2ⁿ.

Qui inviter à la fête

Tu prépares une fête et tu veux inviter quatre amis : Thomas, Julien, Karine et Damien. Le hic, c’est qu’entre eux les relations sont compliquées et que tu aimerais que tout le monde soit content. Après avoir longuement mené l’enquête, tu obtiens six conditions :

Thomas ou Karine vient (ou même les deux).
Julien et Karine ne se supportent pas, donc ils ne viennent pas tous les deux.
Damien ne vient que si Julien vient aussi.
Si Thomas vient, Karine ou Damien doit venir aussi.
Si Thomas et Karine viennent tous les deux, Julien doit venir aussi.
Au moins un des trois, Thomas, Julien ou Damien, vient.

Qui inviter pour que toutes les conditions soient vérifiées en même temps ? Essaie de trouver par toi-même, la solution est cachée à la fin de l’article.

Un informaticien réécrirait le problème dans le langage de la logique propositionnelle. Chaque ami reçoit une lettre, par exemple T comme Thomas. Une lettre est soit vraie (Thomas vient), soit fausse (Thomas ne vient pas). Le symbole ∨ se lit « ou » et ¬ se lit « non ». La première condition s’écrit alors ainsi :

$T \lor K$

La deuxième condition dit que Julien ne vient pas ou que Karine ne vient pas :

$\neg J \lor \neg K$

Pour la troisième condition, on se trompe facilement. « Damien ne vient que si Julien vient aussi » signifie qu’il ne doit pas arriver que Damien vienne et Julien non. Donc soit Damien ne vient pas, soit Julien vient :

$\neg D \lor J$

On réécrit le reste de la même manière. Le problème complet s’écrit alors ainsi :

$\begin{array}{rcl} 1. & T \lor K \\ 2. & \neg J \lor \neg K \\ 3. & \neg D \lor J \\ 4. & \neg T \lor K \lor D \\ 5. & \neg T \lor \neg K \lor J \\ 6. & T \lor J \lor D \end{array}$

Observe à quel point les conditions se ressemblent : quelques lettres, certaines précédées du signe ¬, reliées par le mot « ou ». Et aucune n’a plus de trois lettres. Le problème où l’on a de telles conditions et où l’on cherche comment attribuer aux lettres les valeurs vrai et faux pour qu’elles soient toutes vérifiées en même temps s’appelle 3-SAT. Le trois signifie qu’une condition a au plus trois lettres, et SAT est l’abréviation de l’anglais satisfiability, la satisfiabilité.

À première vue, cela ressemble à un jeu de la page des énigmes. Pourtant, une quantité énorme de problèmes pratiques peut se réécrire sous la forme 3-SAT : les emplois du temps, la vérification qu’une puce de processeur calcule correctement, la planification des horaires de travail ou même le sudoku. Les lettres ne sont alors plus quatre, mais facilement des millions.

Combien de possibilités faut-il essayer ?

La méthode la plus directe consiste à tout essayer. Thomas vient ou ne vient pas, cela fait deux possibilités. Pour chacune d’elles, Julien vient ou ne vient pas, cela fait déjà quatre possibilités. Pour quatre amis, il y en a

$2 \cdot 2 \cdot 2 \cdot 2 = 2^{4} = 16.$

C’est le même raisonnement que pour les vecteurs binaires dans l’article sur P versus NP. Si l’on a n lettres, on peut leur attribuer les valeurs vrai et faux de 2ⁿ façons. Pour 4 amis, cela fait 16 possibilités, que tu passes en revue en quelques minutes. Pour 100 lettres, cela fait

$2^{100} \approx 1, 27 \cdot 10^{30}$

possibilités. Si un ordinateur essayait un milliard de possibilités par seconde, il lui faudrait environ trois mille fois plus de temps que l’âge de l’Univers.

Dans l’autre sens, en revanche, c’est facile : si quelqu’un te dit « invite ces trois-là », tu le vérifies tout de suite. Il suffit de passer en revue les six conditions et de regarder si chacune est vérifiée. Trouver une solution est difficile, la vérifier est facile. Ce sont justement ces problèmes-là que nous avons rangés dans la classe NP dans l’article sur P versus NP.

Mais 3-SAT n’est pas un problème quelconque de NP : en 1971, on a montré que tout problème de NP peut se traduire en 3-SAT. Celui qui saurait résoudre 3-SAT rapidement saurait donc résoudre rapidement absolument tout ce qui se vérifie rapidement. Les problèmes qui ont cette propriété sont dits NP-complets, et 3-SAT en est le représentant le plus célèbre.

Peut-on faire plus vite que 2ⁿ ?

Oui. Tout essayer est inutile. Il suffit par exemple de remarquer que, si Thomas ne vient pas, la première condition impose aussitôt que Karine vienne. Toutes les possibilités où aucun des deux ne viendrait, on les raye d’emblée. Les algorithmes astucieux combinent toute une série d’astuces de ce genre. Les meilleurs connus aujourd’hui ont besoin d’environ

${1,307}^{n}$

étapes. C’est un bond énorme. Pour n = 100, on obtient environ 4,2 · 10¹¹ étapes au lieu de 10³⁰, ce qu’un ordinateur fait en quelques minutes.

Mais attention, il y a un piège. 1,307ⁿ reste une fonction exponentielle. Nous avons réduit la base de deux à 1,307, mais la variable n est restée dans l’exposant. Quand n continuera de grandir, cela finira quand même par nous écraser. Pour n = 1000, même 1,307ⁿ est un nombre de 117 chiffres.

Et à quoi ressemblerait un algorithme qui n’est pas exponentiel ? Par exemple, à un algorithme qui se contente de n³ étapes. Il serait polynomial, et 3-SAT appartiendrait alors à la classe P. Entre les polynômes et les exponentielles, il existe cependant une zone grise : des fonctions qui croissent plus vite que n’importe quel polynôme, et pourtant plus lentement que n’importe quelle exponentielle. Par exemple

$2^{\sqrt{n}} .$

Ici, l’exposant ne contient que la racine carrée de n. Comparons les quatre fonctions dans un tableau :

n	n³	$2^{\sqrt{n}}$	1,307ⁿ	2ⁿ
20	8000	22	212	1 048 576
100	10⁶	1024	4,2 · 10¹¹	1,3 · 10³⁰
1000	10⁹	3,3 · 10⁹	1,9 · 10¹¹⁶	1,1 · 10³⁰¹

Pour n = 1000, $2^{\sqrt{n}}$ joue dans la même catégorie que n³, alors que les deux exponentielles se sont envolées vers des nombres qui n’ont même pas de nom. Les fonctions comme $2^{\sqrt{n}}$ , qui croissent plus lentement que cⁿ pour toute base c supérieure à un, sont dites sous-exponentielles.

Le graphique montre la même chose. L’axe vertical est logarithmique : chaque graduation vers le haut correspond à un nombre cent mille fois plus grand. Sinon, rien d’autre que 2ⁿ ne tiendrait dans la figure.

$Croissance des fonctions 2^n (en rouge), 1{,}307^n (en orange), 2^{\sqrt{n}} (en bleu) et n^3 (en vert), avec un axe vertical logarithmique$

Dans un tel graphique, les exponentielles sont des droites qui montent sans cesse. La rouge 2ⁿ est plus raide que l’orange 1,307ⁿ, mais les deux sont des droites. Ce qui est intéressant, c’est qu’au début l’orange se trouve même sous la verte n³. Elle ne la dépasse que vers n = 42, mais ensuite pour de bon. La bleue $2^{\sqrt{n}}$ , au contraire, s’incurve et reste en bas, près de la verte.

Ce qu’affirme exactement l’ETH

Nous pouvons maintenant énoncer l’hypothèse. Elle a été formulée en 1999 par Russell Impagliazzo et Ramamohan Paturi :

Il existe un nombre c supérieur à un tel qu’aucun algorithme ne peut résoudre 3-SAT à n lettres plus vite qu’en environ cⁿ étapes.

Et en termes simples ? La base de l’exponentielle, nous savons la réduire grâce à des astuces : de deux à 1,5, à 1,307, peut-être un jour à 1,2. Mais nous ne la rapprocherons jamais de un autant que nous le voudrions. Il y a quelque part une limite en dessous de laquelle on ne peut pas descendre. D’après l’ETH, un algorithme de complexité $2^{\sqrt{n}}$ ne devrait donc pas exister.

Pourquoi une hypothèse ? Parce que personne ne sait la démontrer. L’ETH est une hypothèse de travail, un peu comme dans l’article sur P versus NP où nous supposons que P ≠ NP. La plupart des informaticiens y croient, car des décennies d’efforts n’ont permis que de faire descendre lentement la base à partir de deux. Mais personne n’a de démonstration en main.

L’ETH et P versus NP

Quel est le lien entre ces deux questions ? Imagine que 3-SAT ait une difficulté « réelle », celle de l’algorithme le plus rapide possible. Celle-ci peut se trouver dans trois zones :

Trois zones de difficulté de 3-SAT : polynomiale (en vert), sous-exponentielle (en bleu) et exponentielle (en rouge)

Zone verte, polynomiale. 3-SAT peut se résoudre par exemple en n³ étapes. Comme 3-SAT est NP-complet, on aurait alors P = NP, et l’ETH serait évidemment fausse.
Zone bleue, sous-exponentielle. 3-SAT peut se résoudre en $2^{\sqrt{n}}$ étapes ou quelque chose de semblable. Pas en temps polynomial, donc P ≠ NP est vraie. Mais l’ETH serait fausse.
Zone rouge, exponentielle. On ne peut pas faire mieux que cⁿ. L’ETH est vraie, et par conséquent P ≠ NP aussi.

La figure montre que l’ETH est une affirmation plus forte que P ≠ NP. Elle ne dit pas seulement que 3-SAT ne peut pas se résoudre en temps polynomial, mais qu’il ne peut même pas se résoudre en temps sous-exponentiel. Celui qui démontrerait l’ETH démontrerait du même coup P ≠ NP et gagnerait un million de dollars.

Et inversement : celui qui réfuterait l’ETH n’aurait pas forcément démontré P = NP. Un algorithme de la zone bleue lui suffit. Retiens bien cela, nous allons nous en servir dans un instant.

À quoi sert l’ETH

Démontrer qu’un problème ne peut pas se résoudre rapidement est incroyablement difficile en informatique. Nous ne savons presque jamais le faire. L’ETH nous offre une porte dérobée : au lieu de « le problème X est difficile », nous démontrons « le problème X est difficile si l’ETH est vraie ».

Comment ? On montre que, si le problème X pouvait se résoudre rapidement, 3-SAT pourrait lui aussi se résoudre rapidement. Prenons par exemple celui-ci : on a n personnes, et l’on sait que certaines paires de personnes ne se supportent pas. On veut les répartir dans trois salles de sorte qu’aucune de ces paires ne se retrouve dans la même salle. Les informaticiens appellent cela la coloration d’un graphe avec trois couleurs. À partir de chaque problème 3-SAT, on peut en construire un de ce type dans lequel le nombre de personnes n’est qu’un petit multiple du nombre de lettres. Si l’on pouvait donc répartir les personnes dans les salles en temps sous-exponentiel, on pourrait aussi résoudre 3-SAT en temps sous-exponentiel, et l’ETH tomberait.

Des résultats conditionnels de ce genre, il y en a aujourd’hui des centaines. Tout un domaine, qui étudie à quel point exactement les différents problèmes sont difficiles, repose sur l’ETH comme une maison sur ses fondations.

L’ETH a aussi une sœur plus forte, l’hypothèse du temps exponentiel forte (SETH). Elle porte sur les problèmes où les conditions peuvent avoir plus de trois lettres, par exemple dix ou cent. La SETH affirme que plus on autorise des conditions longues, plus la meilleure base possible se rapproche de deux. Pour des conditions longues, on ne pourrait donc presque rien gagner par rapport à l’essai bête et méchant des 2ⁿ possibilités.

Pourquoi on parle de l’ETH en ce moment

L’entreprise OpenAI, que tu connais surtout grâce à ChatGPT, a publié en octobre 2026 une prépublication, c’est-à-dire un article qui n’est pas encore passé par l’évaluation par les pairs. Il s’intitule The Exponential Time Hypothesis is False, en français « L’hypothèse du temps exponentiel est fausse ». OpenAI y affirme avoir trouvé un algorithme qui résout 3-SAT en environ

$2^{\frac{n}{\sqrt{\ln n}}}$

étapes. Dans l’exposant, il n’y a donc pas n tout seul, mais n divisé par la racine carrée du logarithme (népérien). Ce dénominateur croît terriblement lentement, mais il croît, et cela suffit pour que la fonction soit sous-exponentielle. L’algorithme saurait même non seulement trouver une solution, mais aussi compter combien il en existe.

Si c’était vrai, l’algorithme d’OpenAI tomberait dans la zone bleue de la figure ci-dessus. Et qu’est-ce que cela signifierait ?

L’ETH tomberait, et avec elle la SETH et les centaines de résultats conditionnels qui reposaient sur elles. Les informaticiens devraient jeter ou réécrire une foule de « si l’ETH est vraie, alors… ».
Le problème P versus NP ne serait pas résolu. L’algorithme n’est toujours pas polynomial.
En pratique, presque rien ne changerait. La formule cache des constantes que nous ne connaissons pas. Si elles étaient égales à un, pour n = 1000, $\sqrt{\ln n}$ vaudrait environ 2,6 et nous obtiendrions environ 2³⁸⁰ étapes. C’est presque la même chose que 1,307¹⁰⁰⁰ ≈ 2³⁸⁶ pour les meilleurs algorithmes actuels. Le nouvel algorithme ne dépasserait nettement les algorithmes actuels que pour des n encore plus grands, et de combien, cela dépend justement des constantes inconnues. Son intérêt est donc surtout théorique. Ni le chiffrement ni les banques ne sont concernés.

Pour l’instant, il s’agit d’une affirmation non vérifiée. La démonstration est longue et technique, et les spécialistes commencent à peine à la lire. Par le passé, de grandes annonces de problèmes résolus se sont déjà révélées fausses à de nombreuses reprises. Pour l’instant, la règle est donc d’attendre de voir ce qu’en disent les spécialistes. Nous écrivons ce paragraphe le 27 octobre 2026.

Solution du problème de la fête

Tu dois inviter Thomas, Julien et Damien, mais pas Karine. La figure montre les 16 possibilités. Chaque colonne correspond à une possibilité : un rond plein signifie que l’ami vient, un rond vide qu’il ne vient pas. Le chiffre rouge sous la colonne indique la première condition qui n’est pas vérifiée. La seule possibilité pour laquelle toutes les conditions sont vérifiées est encadrée en vert.

Les 16 possibilités de qui inviter. Les lignes correspondent aux amis T, J, K, D ; un rond plein signifie que l’ami vient.

Et c’est exactement cela, la force brute que l’ETH considère comme presque insurmontable : pour quatre amis, seize colonnes, pour cent amis, plus de colonnes qu’il n’y a d’atomes dans notre corps.

Voir aussi

« Précédent: Le plus grand problème de l’informatique : P versus NP

Suivant: Méthode de Trachtenberg pour additionner rapidement »