Dans les années 60, les chercheurs pensaient que P et NP étaient des classes différentes. Mais sans preuve. En 1971, Cook, un mathématicien américain, démontre l'existence d'un problème NP qui, s'il est soluble par une procédure à temps polynomial, prouverait que tous les NP sont des P.
Les enjeux concernent essentiellement la sécurité sur Internet. En effet, le système RSA qui permet le cryptage des messages électroniques dépend du fait que le décryptage du code ne soit pas un problème P. Si on démontrait que s'en était un, la sécurité du système serait compromise.
C'est une énigme qui nécessite une bonne idée inédite, et qui pourrait être résolue par un non matheux. Alors bonne chance !
© Getty images
