La question à 1 000 000 $ : que demande vraiment P vs NP ?

Le problème P vs NP demande si tout problème dont la solution est facile à vérifier est aussi facile à résoudre. En bref : les problèmes faciles à vérifier sont-ils aussi faciles à résoudre?

C'est l'un des sept problèmes du prix du millénaire définis par le Clay Mathematics Institute, chacun doté d'une récompense d'un million de dollars. P vs NP n'a toujours pas été résolu.

Si P était égal à NP, des problèmes aujourd'hui jugés difficiles, comme casser le chiffrement moderne ou optimiser la logistique, deviendraient faciles, bouleversant la cryptographie, la sécurité et l'informatique.