P vs NP
El problema abierto más famoso de la informática. ¿Los problemas que se verifican rápido (NP) también se resuelven rápido (P)? Casi todos creen que no, pero no hay demostración. Premio del Milenio de 1 millón de dólares.
Formulado por Stephen Cook (1971). Si P = NP, toda la criptografía se vendría abajo (RSA y AES descansan sobre supuestos de dureza computacional). Problemas NP-completos (viajante, SAT, mochila): resolver uno rápido = resolverlos todos. Consecuencia práctica: aceptamos que algunos problemas son "difíciles" y usamos heurísticas y aproximaciones (recocido simulado, algoritmos genéticos, relajación lineal). La computación cuántica no mueve la línea — BQP es otra clase de complejidad distinta.