Complexité algorithmique : le fossé entre théorie et pratique
Sommaire
En bref
- Ben Recht critique la définition de « polynomial = efficace » établie par Jack Edmonds en 1965, devenue fondatrice de la théorie de la complexité, en pointant son déconnexion croissante de la réalité computationnelle.
- Les algorithmes « galactiques » (temps polynomial géant ou subexponentiel) ne sont mathématiquement corrects qu'en théorie asymptotique, mais inutilisables en pratique sur des instances réelles.
- Le résultat récent d'OpenAI sur la satisfiabilité (subexponentiel, non polynomial) illustre comment la recherche en complexité peut se perdre dans des améliorations théoriques infimes sans changement d'ordre de grandeur pratique.
Ce que dit la source
L'auteur affirme que la théorie de la complexité, fondée sur la distinction polynomial-exponentiel, a progressivement perdu de vue le problème originel : définir ce qu'un algorithme « efficace » signifie concrètement. Edmonds lui-même, en 1965, admettait l'imperfection de sa définition, craignant qu'elle n'étouffe les algorithmes du monde réel comme le simplexe. Depuis, la discipline s'est construite sur cette approximation fragile, générant un corpus massif de résultats académiques sans ancrage pratique. Le cas d'OpenAI (subexponentiel vs polynomial) exemplifie ce phénomène : amélioration théorique spectaculaire qui ne résout rien pour les instances réelles.
- Edmonds a imposé une limite : un algorithme est « bon » si son temps d'exécution est borné par une fonction bien définie de la taille de l'entrée, quelle que soit cette taille. Cette exigence a disqualifié les énumérations exhaustives mais reste floue sur ce qui rend un polynôme acceptable (n⁴ vs n¹⁰⁸⁰ sont tous deux polynomiaux).
- La distinction polynomial/exponentiel ne s'appuie pas sur une compréhension profonde du problème : c'est plutôt une convention historique devenue dogme. Elle crée une hiérarchie théorique qui ne reflète pas les seuils d'utilité pratique.
- Les algorithmes galactiques (n¹⁰⁸⁰, ou subexponentiels comme celui d'OpenAI) sont correctement formalisés sur le plan mathématique mais complètement détachés des instances qu'on rencontrerait jamais, même sur une durée cosmique.
- Le résultat d'OpenAI en satisfiabilité (subexponentiel, pas polynomial) n'invalide pas vraiment l'Exponential Time Hypothesis fondamentale : il ne franchit pas la frontière théorique attendue, ce qui limite sa portée conceptuelle.
Dans les commentaires
Débat partagé, avec plusieurs critiques pointues. Une partie des commentateurs récuse la thèse centrale, jugeant que la distinction polynomial/exponentiel a trouvé un fondement solide au-delà de l'arbitraire. D'autres reconnaissent le problème gap théorie/pratique mais contestent l'utilité du reproche sans proposition alternative viable. Un commentateur souligne l'ironie : l'auteur critique l'absence de rigueur intellectuelle dans le champ tout en admettant ne pas avoir lu les papiers qu'il commente.
- Plusieurs commentateurs s'opposent au cœur de la critique : si le choix polynomial/exponentiel était quasi-arbitraire à l'origine, il a depuis acquis une justification solide. L'exponentiel émerge naturellement des algorithmes par énumération et vérification, tandis que le polynomial révèle une structure du problème exploitable. Même un polynôme gigantesque reste mathématiquement intéressant car il suggère que tout problème facile à vérifier porte une structure cachée.
- Un commentateur signale l'absence de proposition alternative : critiquer la complexité asymptotique sans offrir un cadre de remplacement tout aussi tractable et composable paraît incomplet.
- Plusieurs souligent que le problème (big constants vs asymptotique) est connu depuis longtemps (voir l'évolution des exposants en multiplication matricielle), ce qui amoindrit la nouveauté du reproche.
- Une critique acérée note que l'auteur s'était vanté de ne pas avoir lu le papier d'OpenAI, une stance qui limite sa crédibilité à critiquer le résultat lui-même.
- Un point isolé : le résultat d'OpenAI n'est impressionnant que s'il cache son recours à une énumération brute sur des instances petites, avec un seuil astronomiquement grand au-delà duquel la complexité reprend ses droits.
Notre lecture
La critique d'une déconnexion entre théorie asymptotique et problèmes réels est fondée, mais elle ne débouche ici que sur un diagnostic, pas sur une solution opératoire. L'auteur pointe juste que les « galactic algorithms » sont une chimère académique, et que la convention polynomial-exponentiel reste imparfaite. Cependant, les commentateurs ont raison de souligner que cette convention a néanmoins une structure mathématique interne (énumération vs. exploitation de structure) qui persiste une fois qu'on la regarde correctement. Le vrai défi (prouver qu'un algorithme polynomial pour NP doit être galactique) reste ouvert, et aucun analyste n'a su le résoudre. Pour les DSI et tech leads, ce débat n'a guère de conséquence immédiate : la complexité asymptotique reste un outil imparfait mais utilisable pour choisir entre des algorithmes et détecter les pires cas. Le piège n'est pas la théorie, c'est d'oublier de valider sur les données réelles, ce qui était vrai en 1965 et l'est toujours.