Le million de dollars caché dans une question toute bête

Et si vérifier une réponse était aussi facile que la trouver ? C'est précisément la question qui vaut un million de dollars depuis 2000. Le problème P ≟ NP demande : si je peux rapidement vérifier que tu as résolu un puzzle (en temps polynomial), peux-tu le résoudre aussi vite ? Prenons un exemple concret : factoriser un nombre géant en produit de nombres premiers. Vérifier que deux nombres multipliés ensemble donnent ce géant ? Facile et rapide. Mais trouver ces deux nombres ? Excessivement dur, même pour les ordinateurs les plus puissants. Si P = NP était vrai, alors trouver serait aussi facile que vérifier — ce qui révolutionnerait cryptographie, optimisation, tout. Si P ≠ NP (le consensus actuel), certains problèmes resteront intrinsèquement plus durs à résoudre qu'à contrôler. L'Institut Clay a promis un million de dollars à qui le prouvera : et personne ne l'a encore empoché.