El problema de P versus NP se considera el problema abierto más importante en la ciencia de la computación. De hecho el Instituto Clay lo incluye entre los 7 “problemas del milenio”, que corresponden a los problemas matemáticos abiertos más importantes según ese instituto.