Galardonado el padre del mayor misterio de la computación

En el universo existen miles de problemas denominados NP que, aunque es rápido formularlos y verificar si una solución dada para ellos es correcta, el ordenador más potente necesitaría miles de millones de años para resolverlos de forma definitiva. Entre ellos está el cálculo de la ruta más corta que pase por multitud de puntos, la solución de los sudokus o determinar la forma en la que deben plegarse las proteínas para funcionar correctamente. Los matemáticos no saben si son tan laboriosos de forma intrínseca, o si es que a nadie se le ha ocurrido todavía el algoritmo adecuado para resolverlos. Los problemas P, por su parte, son los que se pueden dilucidar en un plazo de tiempo razonable.

Nadie sabe si los problemas P y los NP son equivalentes. Si solo hace falta descubrir el algoritmo que resuelva estos últimos de forma eficiente, o si pertenecen a categorías de complejidad diferentes. De momento, en el plano práctico, todo el mundo asume que la segunda opción es la correcta mientras no se demuestre lo contrario. Cuando un científico o un ingeniero se encuentra con un reto NP en su trabajo, asume que la solución perfecta está fuera de su alcance y que debe contentarse con una aproximación razonable que su ordenador pueda dirimir en un tiempo prudencial. Estos aparecen en toda clase de disciplinas: en biología, en economía, en física, en matemáticas y en ingeniería. "Si puedes demostrar que es NP, ningún jefe podrá echarte la bronca por no poder resolverlo. Muchos de los más grandes matemáticos lo han intentado sin éxito", ha bromeado Georg Gottlob, catedrático de Computación en Oxford y presidente del jurado que ha concedido el premio a Cook.

En la supuesta complejidad de NP se basan, también, la mayoría de sistemas de cifrado de las comunicaciones que se usan en la actualidad. Los que permiten pagar de forma segura a través de internet, o usar la página web del banco sin que nadie pueda espiar ni alterar las cuentas del usuario. Si alguien descubriese que P y NP son equivalentes, toda esta tecnología dejaría de ser eficaz casi al instante.

"Alan Turing determinó en 1935 qué problemas podía o no resolver un ordenador", ha explicado Cook en una conversación telefónica después de que se hiciese público su galardón. "Mi aportación fue la Completitud NP, y determinar que si puedes resolver un problema NP Completo, puedes resolverlos todos". Es decir, que si alguien demuestra que un único problema NP de su variante más difícil denominados completos tiene una solución en un plazo razonable, se podrá usar la misma idea para encontrarla en todos los demás.

Cook sospecha, como casi todo el mundo, que P y NP no son equivalentes. "Hace muchos años me dediqué a tratar de demostrar que eran distintos, sin éxito, pero ya no", ha asegurado. "Es un reto muy difícil al que se enfrentan algunos de los mejores matemáticos del mundo y, aun así, supongo que todavía harán falta muchos años para que alguien lo demuestre".