P vs NP: un problema que vale un millón de dólares

Comprobar que un sudoku está bien resuelto es rápido. Resolverlo desde cero, mucho más lento. La pregunta P vs NP formaliza esa intuición: ¿todo problema cuya solución se verifica rápido se puede también resolver rápido?

Es uno de los siete Problemas del Milenio: quien lo resuelva se lleva un millón de dólares del Instituto Clay.

Por qué importa tanto

Si P fuera igual a NP, muchos problemas hoy “imposibles” —romper cifrados, optimizar rutas, plegar proteínas— se volverían tratables. La seguridad de internet se apoya, en el fondo, en que casi todos creemos que P ≠ NP.