🎛️ Le mur exponentiel
Augmente la taille n du problème. Compare le temps de résolution selon la complexité de l'algorithme. Le polynomial reste maniable, l'exponentiel explose.
O(n) lin.
20 ns
O() quad.
400 ns
O() exp.
1 µs
O(n!) fact.
—
À n = 20, le polynomial est instantané, l'exponentiel encore gérable. Augmente n pour voir le mur.
🔍 P et NP : deux mondes de problèmes
En informatique théorique, on classe les problèmes par leur complexité : combien d'opérations faut-il pour les résoudre en fonction de la taille n de l'entrée ?
- Classe P (Polynomial time) : problèmes résolubles en temps polynomial. Pour une entrée de taille n, il existe un algorithme en O(n^k) pour un certain k fixe. Exemples : trier une liste (O(n log n)), trouver le plus court chemin (Dijkstra, O((V+E) log V)), résoudre un système linéaire (Gauss, O()).
- Classe NP (Nondeterministic Polynomial time) : problèmes dont une solution candidate peut être vérifiée en temps polynomial. Mais trouver cette solution peut être beaucoup plus long. Exemples : Sudoku, voyageur de commerce, factorisation d'un grand nombre.
Question P vs NP :
Tout problème dont la solution est vérifiable en temps polynomial
est-il aussi résoluble en temps polynomial ?
Autrement dit : P = NP ou P ≠ NP ?
🎓 1971 : Cook et Levin posent le problème
Stephen Cook (Toronto, 1971) et Leonid Levin (URSS, 1973, indépendamment) publient les fondations de la théorie. Cook introduit la notion de NP-complétude :
Un problème est NP-complet s'il est dans NP et si tous les autres problèmes NP peuvent s'y réduire en temps polynomial. Autrement dit : c'est l'un des problèmes les plus difficiles de NP. Si on résout efficacement un seul problème NP-complet, on résout efficacement tous les problèmes NP.
Cook prouve que SAT (satisfiabilité booléenne) est NP-complet. C'est le premier exemple historique.
🏆 Exemples de problèmes NP-complets
- SAT (satisfiabilité booléenne) : étant donné une formule booléenne, existe-t-il une assignation de variables qui la rende vraie ? Le problème originel de Cook (1971).
- 3-coloration : peut-on colorier un graphe avec 3 couleurs sans que deux voisins partagent la même ? (Avec 4, c'est toujours possible — théorème vu juste avant. Avec 3, NP-complet.)
- Voyageur de commerce (TSP) : trouver le plus court circuit visitant n villes exactement une fois.
- Sac à dos : choisir parmi des objets de poids/valeur donnés pour maximiser la valeur sans dépasser une capacité.
- Sudoku généralisé (×) : NP-complet.
- Problème de Hamilton : trouver un cycle qui passe par chaque sommet d'un graphe une fois.
- Subset Sum : étant donné des entiers et une cible S, trouver un sous-ensemble dont la somme vaut S.
- Démineur, Tetris, Pac-Man : leurs versions généralisées sont NP-difficiles.
Aujourd'hui, on connaît plus de 3 000 problèmes NP-complets. Ils viennent de tous les domaines : logique, théorie des graphes, optimisation, biologie, économie, cryptographie.
💰 2000 : l'un des 7 problèmes du millénaire
En 2000, le Clay Mathematics Institute classe P vs NP parmi ses 7 problèmes du millénaire. 1 million de dollars pour qui résoudra la question dans un sens ou dans l'autre.
Conviction quasi-unanime des chercheurs : P ≠ NP. Mais aucune preuve. Un sondage de 2019 auprès de 152 experts donnait 88 % en faveur de P ≠ NP, 12 % en faveur de P = NP ou indécidable.
🔮 Conséquences si P = NP
Imagine qu'un mathématicien démontre P = NP avec un algorithme polynomial constructif pour SAT. Effets en cascade :
- Cryptographie cassée : RSA, ECC, AES (clés) reposent sur le fait que factoriser ou inverser certains problèmes est dur. Si P = NP, on factorise rapidement → tous les chiffrements actuels tombent. Bitcoin, banques en ligne, communications militaires : compromis du jour au lendemain.
- Optimisation universelle : tournées de livraison, planification industrielle, ordonnancement, allocation de ressources — tous résolus en temps polynomial.
- Biologie : repliement de protéines (DeepMind AlphaFold est une approximation géniale, mais le problème exact est NP-difficile). Conception de médicaments, génomique.
- IA : apprentissage optimal, raisonnement automatique. Une IA capable de prouver des théorèmes mathématiques aussi efficacement qu'elle les vérifie.
- Mathématiques : trouver une preuve de longueur bornée devient trivial. Beaucoup de conjectures s'effondreraient (ou se résoudraient).
- Économie : marchés efficients, optimisation globale, équilibre général.
🛡️ Conséquences si P ≠ NP
L'hypothèse standard. Si on la prouve formellement :
- Cryptographie validée : nos chiffrements restent fondamentalement sûrs (au moins classiquement — l'ordinateur quantique reste une menace séparée).
- Limites de l'IA : certains problèmes resteront intrinsèquement difficiles, même pour l'IA la plus avancée. L'optimisation parfaite est hors d'atteinte.
- Liberté de la créativité : si trouver des preuves élégantes était polynomialement aussi facile que les vérifier, la créativité mathématique perdrait son mystère. P ≠ NP, c'est aussi la dignité de l'invention.
🌟 Au-delà de P et NP
Le « zoo de la complexité » a aujourd'hui plus de 500 classes connues. Quelques autres :
- co-NP : problèmes dont la non-solution est vérifiable rapidement. Question ouverte : NP = co-NP ?
- PSPACE : problèmes résolubles avec un espace mémoire polynomial. Contient NP. Question ouverte : NP = PSPACE ?
- EXPTIME : temps exponentiel. On sait que P ⊊ EXPTIME (théorème de hiérarchie en temps).
- BQP (Bounded-error Quantum Polynomial) : problèmes résolubles efficacement par un ordinateur quantique. Contient la factorisation (Shor 1994). Question : BQP ⊋ P ? Probablement oui, mais non prouvé.
- #P : compter les solutions au lieu d'en trouver une. Beaucoup plus dur que NP en général.
- Indécidable : problèmes pour lesquels aucun algorithme n'existe (problème de l'arrêt de Turing). Au-delà de tout.
🚧 Pourquoi c'est si difficile à prouver
Plusieurs barrières théoriques ont été identifiées :
- Barrière de relativisation (Baker-Gill-Solovay 1975) : certaines preuves « marcheraient pour des oracles donnant P = NP, d'autres pour P ≠ NP ». Donc aucune technique « locale » ne peut trancher.
- Barrière des preuves naturelles (Razborov-Rudich 1997) : sous une hypothèse cryptographique standard, aucune preuve « naturelle » ne peut prouver P ≠ NP.
- Barrière de l'algébrisation (Aaronson-Wigderson 2008) : même les méthodes algébriques sophistiquées ne suffisent pas.
Conclusion : il faudra une approche fondamentalement nouvelle. C'est pourquoi beaucoup pensent qu'on est encore loin d'une solution.
📐 Le lien avec ton programme
- Logique : SAT est le problème NP-complet de base. La logique propositionnelle est implicitement vue en démonstration (et, ou, non, implication).
- Dénombrement : comprendre pourquoi croît plus vite que tout n^k est essentiel. Programme dénombrement 2BAC.
- Suites : croissance comparée polynomiale vs exponentielle vs factorielle. Limite et asymptote. Programme 2BAC SM.
- Récurrence : la plupart des algorithmes NP-difficiles ont une formulation récursive (backtracking, branch-and-bound).
- Probabilités : les algorithmes probabilistes (Monte Carlo, Las Vegas) permettent de contourner partiellement la difficulté de certains NP-difficiles.
🎯 En pratique : on s'en sort comment ?
Si P ≠ NP, comment résoudre les problèmes NP-difficiles dans la vraie vie ?
- Approximation : trouver une solution à 1.5× l'optimal au lieu de l'optimal exact. Pour le voyageur de commerce, l'algorithme de Christofides garantit 1.5×.
- Heuristiques : recuit simulé, algorithmes génétiques, recherche locale. Pas de garantie, mais souvent excellents en pratique.
- SAT solvers modernes : Z3 (Microsoft), MiniSat, CryptoMiniSat — résolvent des instances avec des millions de variables, alors que le pire cas reste .
- Cas particuliers : certains sous-cas de problèmes NP-difficiles deviennent polynomiaux (2-SAT, 2-coloration).
- Machine learning : DeepMind AlphaFold (repliement protéique), AlphaGo (Go), AlphaProof (preuves mathématiques) — résolvent en pratique des problèmes formellement NP-difficiles.
Vérifie ta compréhension
3 questions courtes pour valider tes acquis. Tu peux réessayer.