OpenAI et Anthropic affirment réfuter l'hypothèse du temps exponentiel
Sommaire
En bref
- OpenAI et Anthropic ont publié presque simultanément des preuves affirmant que l'hypothèse du temps exponentiel (ETH) est fausse, montrant que 3-SAT admet un algorithme en temps subexponentiel.
- Ces résultats ne s'étendent pas automatiquement à tous les problèmes NP via les réductions standards, et leur portée pratique reste extrêmement limitée.
- Le débat HN porte sur la validité réelle de ces preuves, leurs limites théoriques, et si elles constituent un véritable progrès ou reposent sur des artefacts mathématiques.
Ce que dit la source
OpenAI a publié une preuve affirmant que l'hypothèse du temps exponentiel (ETH), le postulat que 3-SAT ne peut pas être résolu mieux que 2^n, est fausse. La preuve exhiberait un algorithme en temps 2^o(n) pour 3-SAT. Anthropic a simultanément publié une preuve similaire avec des bornes équivalentes mais via une approche différente. Ces résultats s'inscrivent dans une série de découvertes théoriques récentes (FFT accélérée, multiplication entière rapide) qui remettraient en question les intuitions de la génération post-Karp en complexité.
- L'algorithme subexponentiel 2^o(n) ne transfère pas aux problèmes NP généraux : réduire un problème NP à 3-SAT en temps polynomial puis le résoudre en subexponentiel ne garantit pas une solution globale subexponentielle, contrairement à ce que ferait une réduction linéaire en nombre de variables.
- Le résultat s'applique néanmoins aux problèmes réductibles à 3-SAT via une transformation préservant la taille (nombre linéaire de variables) : comptage des ensembles indépendants, coloriages propres, couplages parfaits.
- La borne pratique où l'affirmation devient valide est n > 2^10^9, un ordre de grandeur si immense que décrire l'instance dépasserait les limites physiques de l'univers observable.
- Le doute principal porte sur la construction : comment l'algorithme traite les instances 'petites' (via énumération et lookup) versus 'grandes' (via méthode polynomiale) reste opaque et critiqué comme une utilisation de cheating via énumération plutôt qu'une réduction algorithmique fondamentale.
Dans les commentaires
Débat très polarisé et partagé. Le fil célèbre l'inattendu et rappelle Knuth (qui n'a jamais exclu P=NP), mais plusieurs commentateurs expérimentés contestan la validité des preuves sur des bases mathématiques solides, en particulier le recours à l'énumération en lookup pour le cas 'petit'.
- Plusieurs commentateurs questionnent si la construction relève vraiment d'un algorithme plutôt que d'un artefact mathématique : réduire à énumérer tous les cas jusqu'à une limite, puis utiliser une formule polynomiale au-delà, apparaît comme contourner le problème plutôt que le résoudre.
- Un lien vers un commentaire (tomaskafka) mentionne qu'aucun résultat sensible à la cryptographie n'a été publié, suggérant une possible censure par les agences de renseignement, observation hautement spéculative et non vérifiable via les commentaires fournis.
- Le saut d'échellepose un défi pratique insurmontable : n > 2^10^9 rend tout test empirique ou application réelle impossible.
- Plusieurs commentaires notent que ce résultat disproportionné en médias/attrait ne change rien pour P vs NP lui-même (l'intuition dominante reste P≠NP) et demande si c'est véritablement un progrès ou une accumulation d'optimisations incrémentales sur une preuve fragile.
- Aucun SAT-solver expérimenté présent dans le fil pour juger l'applicabilité pratique immédiate.
Notre lecture
Le résultat est mathématiquement inattendu et mérite attention, mais sa validité et son intérêt réel restent en suspens. Les sceptiques ont des points durables : la construction s'appuie sur une séparation cas-petit/cas-grand où le petit ne coûte rien parce qu'énuméré et mémorisé, ce qui ne constitue pas un algorithme standard. La pertinence pratique est nulle (n > 2^10^9). Pour la théorie de la complexité, c'est intéressant à suivre, ces preuves seront étudiées, formalisées, et acceptées ou réfutées par les experts, mais aucune action n'en découle pour une équipe d'ingénieurs. Ni une percée paradigmatique, ni un bruit : une affirmation théorique contestée qui dépendra de sa validation en peer-review.