Stephen Cook, Premio Fundación BBVA Fronteras del Conocimiento en Tecnologías de la Información
El matemático estadounidense Stephen Arthur Cook ha sido galardonado con el Premio Fundación BBVA Fronteras del Conocimiento en Tecnologías de la Información y la Comunicación por demostrar que hay problemas que los ordenadores no son capaces de resolver en un tiempo razonable.
Cuando nos encontramos ante una de estas cuestiones (los llamados problemas NP) es mejor buscar una aproximación, en lugar de desperdiciar esfuerzos persiguiendo un imposible. “Son problemas que, en principio, podrían ser resueltos por un ordenador, pero la máquina tardaría tanto que el sol moriría antes", explica Cook.
El trabajo de Stephen Cook, catedrático de Ciencias de la Computación en la Universidad de Toronto, ha tenido un impacto decisivo en campos como la biología, la física, la economía o la cibernética, donde los cálculos complejos son de vital importancia.
El jurado internacional del Premio Fundación BBVA Fronteras del Conocimiento ha considerado que su aportación es, junto al concepto de “computabilidad” de Alan Turing, uno de los hitos de la matemática de la computación. Si Turing definió qué pueden resolver los ordenadores y qué no, Cook incorporó el principio de eficiencia para determinar qué pueden resolver de forma eficiente y qué no.
En este vídeo puedes ver la primera entrevista ofrecida por Stephen Cook tras la concesión del premio.
Implicaciones para los sistemas de encriptado y seguridad informática
La principal aportación de Cook fue determinar que, dentro de estos problemas NP (no solubles eficientemente), había un tipo, que llamó NP-Completos, que, además de ser los más difíciles, son computacionalmente equivalentes. Actúan como una llave, de forma que, si se hallara un algoritmo eficiente para uno de ellos, “entonces todos los problemas NP podrían resolverse fácilmente”, afirma Cook. Y las implicaciones serían enormes, porque comprometería el sistema de encriptado –fundamentado en problemas NP– y la seguridad en que se basa toda la economía digital.
Sin embargo, la inmensa mayoría de los matemáticos cree que no hay un algoritmo así, y que por tanto los problemas NP realmente son irresolubles. Pero nadie lo ha demostrado.
Problema del Milenio
El trabajo de Cook dio lugar también al que hoy es considerado uno de los principales problemas sin resolver de las matemáticas: el problema de "P (problemas fácilmente solubles) versus NP". Es uno de los siete problemas incluidos en la lista de Problemas del Milenio del Clay Mathematics Institute (EE.UU.), cuya resolución se premia con un millón de dólares.
Hoy se conocen miles de problemas NP-Completos en ámbitos muy diversos: biología, física, economía, teoría de números, lógica, optimización… Un ejemplo es la forma en que las proteínas adquieren su estructura tridimensional, un problema esencial en biología; otro es el famoso problema del viajante: hallar la ruta más eficiente que debe seguir un repartidor para llegar a muchos destinatarios.
El problema "P versus NP” se pregunta si de verdad no existe ninguna otra manera más rápida, ningún atajo brillante, que permita resolver estos problemas. Por ejemplo, en el problema del repartidor, hoy por hoy la única manera de hallar la ruta más rápida es calcular todas las trayectorias posibles; es un problema NP porque cuando los destinatarios son muchos hay que hacer tantos cálculos que en la práctica el problema es irresoluble. Pero ¿seguro que no existe un algoritmo que dé una solución sin necesidad de hacer todos esos cálculos? Eso es lo que plantea el problema "P versus NP”.
Sin embargo, como explica el acta del Jurado, 45 años de esfuerzos combinados de informáticos y matemáticos no han servido para hallar este algoritmo eficiente para los problemas NP-Completos.