Premio Fundación BBVA al matemático del millón de dólares

El Clay Mathematics Institut elaboró la lista de los siete "Problemas del Milenio", cuya resolución se premia con un millón de dólares debido a su enorme complejidad. Y entre ellos se encuentra el planteado por el matemático Stephen Cook (1939), catedrático de Ciencias de la Computación en la Universidad de Toronto, y cuyos trabajos en la computación le han hecho valedor del Premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnología de la Información y la Comunicación. Así, el jurado reconoció esta mañana "su importante papel a la hora de determinar qué pueden resolver los ordenadores de forma eficiente y qué no", un trabajo que "ha tenido un impacto decisivo en todos aquellos campos en los que los cálculos complejos son de vital importancia". Y es que, si Alan Turing definió qué pueden resolver los ordenadores y qué no, Cook, ya desde su primer trabajo en 1971, incorporó el principio de eficiencia para determinar qué pueden o no pueden resolver de forma eficiente.

Existen tres tipos de problemas a los que se enfrenta un ordenador. Están los problemas P, que pueden ser resueltos en un tiempo razonable. Después están los NP, que, en principio, "pueden ser resueltos por un ordenador, pero la máquina tardaría tanto que el sol moriría antes", explicó ayer el matemático "sorprendido y encantado"tras conocer la decisión del jurado. Y después están los que teorizó Cook, los NP completos: además de ser los más difíciles, si se hallara un algoritmo eficiente para ellos, significaría que existe un algoritmo para el resto de problemas. Este concepto de NP completo, explican en la Fundación BBVA, se considera "uno de los principios fundamentales de la ciencia de la computación". De hecho, existen miles de estos problemas planteados en ámbitos como la biología, la física, la economía, la teoría de números. Un ejemplo es el famoso problema del viajante: ¿cuál sería la ruta más eficiente que debe seguir un repartidor para llegar a muchos destinatarios? De esta forma, los problemas NP completos son de especial importancia para científicos e ingenieros, así como para los técnicos informáticos que diseñan algoritmos.

Y así nació el "problema del milenio". Concretamente, el problema "P versus NP", que se pregunta si no existe un atajo brillante que permita resolver los problemas NP. Volviendo al ejemplo del repartidor, la única manera de hallar la ruta más rápida es calcular todas las trayectorias posibles. Se trata de un problema NP porque, al ser muchos los destinatarios, hay que elaborar tantos cálculos que, en la práctica, el problema es irresoluble. De hecho, la mayoría de matemáticos cree que no existe un algoritmo que resuelva este problema y que, por lo tanto, los NP no tienen solución. Al plantear los problemas NP completos, mucho más complejos, Cook señala que, si alguien encuentra un algoritmo para resolverlos, entonces todos los problemas NP "podrían resolverse fácilmente". La solución a este problema, que nadie ha conseguido resolver, tendría enormes implicaciones, pues se comprometería el sistema de encriptado de los ordenadores y su seguridad, que son la base de la economía digital.