Galardonado el padre del mayor misterio de la computación
Stephen Cook recibe el Premio Fundación BBVA por su formulación del conocido como problema P contra NP.
El científico computacional Stephen Cook recibió ayer el Premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación por formular el principal reto al que se enfrentan los investigadores de su especialidad. Un dilema matemático que, de momento, nadie ha logrado resolver y que se incluye entre los siete Problemas del Milenio; si alguien lo demuestra o lo refuta recibirá un millón de dólares. Según en qué sentido se resuelva, además, podría hacer añicos las principales tecnologías de cifrado de las comunicaciones en vigor en la actualidad. El problema, entre la comunidad científica, se conoce como P contra NP.
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.