C’est fou

5/10

IAThe PrimeTime28 octobre 2026 à 21:4511:28

Lecteur audio

INTRO

Un nouvel algorithme prétendument sous-exponentiel pour 3-SAT remettrait en cause l’hypothèse du temps exponentiel, mais il ne montrerait pas P = NP et, à lui seul, ne briserait pas le chiffrement moderne.

POINTS CLÉS

Ce qui est affirmé

L’affirmation centrale est une méthode plus rapide pour résoudre 3-SAT, un problème canonique NP-complet dans lequel il faut attribuer aux variables les valeurs vrai ou faux de sorte que chaque clause de trois littéraux soit satisfaite. Le temps d’exécution annoncé est d’environ 2^n / sqrt(log n), ce qui reste énorme mais croît légèrement moins vite qu’une borne purement exponentielle. C’est important, car l’hypothèse du temps exponentiel soutient que des problèmes comme 3-SAT ne peuvent pas être résolus en temps sous-exponentiel.

Pourquoi 3-SAT est important

3-SAT est l’un des problèmes de référence les plus connus en théorie de la complexité, car beaucoup d’autres problèmes difficiles peuvent s’y réduire. Si un algorithme nettement meilleur existe pour 3-SAT, il peut remodeler les attentes pour une vaste classe de problèmes d’optimisation et de recherche. Son importance est d’abord théorique: cela change ce que les chercheurs pensent possible, même avant toute application pratique.

Ce que dit ETH

L’hypothèse du temps exponentiel est plus forte que la question non résolue P versus NP. Elle ne dit pas seulement qu’il n’existe pas d’algorithme en temps polynomial pour 3-SAT; elle affirme qu’aucun algorithme ne peut éviter une croissance essentiellement exponentielle lorsque la taille de l’entrée augmente. Un temps d’exécution comme 2^n / sqrt(log n) contredirait donc cette hypothèse, car il est techniquement sous-exponentiel, même s’il reste bien trop grand pour des instances réelles de taille sérieuse.

Pourquoi cela ne signifie pas P = NP

Une amélioration sous-exponentielle n’est pas la même chose qu’une percée en temps polynomial. P = NP exigerait un algorithme dont le temps d’exécution soit borné par un polynôme comme n^2 ou n^10, et non par une fonction toujours dominée par 2^n. Le résultat revendiqué constituerait donc une avancée majeure en théorie de la complexité sans résoudre le problème ouvert le plus célèbre de l’informatique.

Quelle est l’ampleur de l’amélioration

Même des changements modestes en apparence dans les exposants peuvent être mathématiquement significatifs. Les chercheurs ont depuis longtemps grignoté la recherche exhaustive avec des bases inférieures à 2, y compris des algorithmes autour de 1.3^n pour certaines formulations, mais ceux-ci explosent encore rapidement. Pour de grandes entrées, toute fonction de la forme c^n reste impraticable, et la nouvelle borne revendiquée ne rendrait pas soudainement solvables de gigantesques instances NP-complètes sur le matériel actuel.

Pourquoi le débat sur la sécurité est exagéré

Le passage de l’affaiblissement de ETH à « tout le chiffrement est cassé » est excessif. Des systèmes comme RSA reposent sur la factorisation entière, supposée difficile mais non connue comme NP-complète. Un algorithme plus rapide pour 3-SAT ne fournit pas automatiquement un algorithme polynomial pour la factorisation, et ne casse pas instantanément les fonctions de hachage, HMAC, les générateurs pseudo-aléatoires ni les blockchains.

Ce qu’il faudrait pour un choc sociétal

Le scénario vraiment disruptif serait une preuve qu’un problème NP-complet peut être résolu en temps polynomial. Comme les problèmes NP-complets sont interréductibles, un algorithme polynomial pour l’un d’eux se transférerait à beaucoup d’autres, de l’acheminement et l’ordonnancement à la résolution d’énigmes et à certaines parties de la biologie computationnelle. Cela pourrait accélérer les découvertes dans des domaines comme la conception de médicaments, mais obligerait aussi à repenser de nombreuses hypothèses de sécurité.

Prudence pratique

Les affirmations extraordinaires en théorie de la complexité exigent un examen approfondi et une vérification indépendante. Même si les mathématiques sont correctes, le résultat peut rester surtout conceptuel plutôt qu’immédiatement exploitable. Les percées en complexité modifient souvent la carte de ce qui est démontrable bien avant de changer l’informatique au quotidien.

CONCLUSION

Un algorithme sous-exponentiel pour 3-SAT constituerait une remise en cause sérieuse de l’hypothèse du temps exponentiel et un résultat notable en informatique théorique. Mais cela ne voudrait pas dire P = NP, et cela ne provoquerait pas, à lui seul, l’effondrement de la cryptographie moderne.

Poser une question

Sur le même sujet : IA