p vs np

P versus NP

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. El premio por resolver alguno de estos problemas es de un millón de dólares. La descripción del Instituto Clay sobre el problema P versus NP es más o menos la siguiente: