le problème P = NP est un problème non résolu, et est considéré par de nombreux chercheurs comme un des plus importants problèmes du domaine.  L'Institut de mathématiques Clay a inclus ce problème dans sa liste des 7 problèmes du prix du millénaire.