Aller au contenu
L’athanor
L’athanor
Connexion

P = NP ?

Aubin

Mathphilo

Sans titre

En une phrase sèche : P = NP ? revient à demander si tout problème dont on peut vérifier vite la solution peut aussi se résoudre vite.

Partons des images simples. Vérifier une solution, c’est inspecter un Sudoku déjà rempli : en quelques gestes, vous savez si les règles tiennent. Trouver la solution, c’est traverser un labyrinthe de possibilités. La question oppose ces deux gestes : le contrôle expéditif et la recherche coûteuse.

En langage de complexité :

  • P = problèmes décidables en temps polynomial par un algorithme déterministe — un temps qui croît “raisonnablement” (n^k) quand la taille de l’entrée augmente.
  • NP = problèmes pour lesquels un certificat (solution candidate) peut être vérifié en temps polynomial.

On sait que P \subseteq NP. La question : existe-t-il des problèmes qu’on peut vérifier vite mais pas résoudre vite ?

  • Si P = NP : trouver est fondamentalement équivalent à vérifier.
  • Si P \neq NP : trouver peut être structurellement plus dur que vérifier — pour Peirce, l’abduction (invention d’hypothèses) resterait d’une autre nature que la déduction.

Exemples :

  • Sudoku : vérifier une grille correcte est trivial ; en générer une parfaite est beaucoup plus ardu.
  • Voyageur de commerce : calculer la longueur d’une tournée donnée est immédiat ; trouver la plus courte parmi toutes croît en difficulté de façon explosive.

Pivot historique : début 1970, Cook et Levin identifient des “problèmes carrefours” — NP-complets — dont SAT (satisfiabilité booléenne). Si l’un d’eux tombe en polynomial, tous les problèmes de NP tombent avec.

Conséquences si P = NP :
1. Cryptographie : RSA, ECC, etc., s’effondrent — leur sécurité repose sur l’asymétrie entre trouver et vérifier.
2. Optimisation : planification, conception, design moléculaire — tout deviendrait calculable à l’optimal comme routine.
3. Preuves : si vérifier est rapide, trouver des preuves complètes le deviendrait aussi.

Conséquences si P \neq NP :

  • Justification des heuristiques, algorithmes d’approximation, paramétrisations fines, et recours stratégique au hasard ou à l’apprentissage automatique : palliatifs efficaces mais non universels.

Pourquoi indécidable aujourd’hui ? Les approches connues se heurtent à des barrières théoriques (relativisation, natural proofs, algebrization). Toute percée exigera une idée radicalement neuve.

Consensus : la communauté penche pour P \neq NP, sans preuve formelle. Le Clay Mathematics Institute offre 1 M$ pour une démonstration.

Image finale :

  • P = NP : chaque serrure a sa clé rangée juste dessous le paillasson.
  • P \neq NP : la clé existe, mais la forger exige patience, invention et détour — et l’intelligence, humaine ou machinique, s’y exerce dans l’entre-deux du possible et du vérifiable.