Alan Turing describió por primera vez en 1936 el concepto de computabilidad y detalló qué problemas puede resolver o no un ordenador. A esta idea, el matemático Stephen Cook (Nueva York, 1939) añadió la eficiencia: saber si un problema se puede resolver en un tiempo asumible —y el tiempo es la clave— es esencial para decidir si merece la pena insistir en solucionarlo o resignarse y buscar una conclusión aproximada. Con esta idea, el matemático ha ganado el Premio Fronteras del Conocimiento de Tecnologías de la Información, otorgado hoy por la Fundación BBVA.

Stephen Cook ha conseguido el galardón por determinar que hay problemas que los ordenadores no pueden resolver de manera eficiente. “En ese caso, lo más inteligente es dejar de intentarlo. Eso permite a los programadores ensayar estrategias mucho más útiles”, explica Cook.

En concreto, el matemático dividió los problemas en dos categorías: los que pueden ser resueltos en un tiempo razonable, a los que llamó P, y aquellos que implicarían tanto tiempo que “el sol se apagaría antes”, a los que llamó NP.

Para estos últimos definió una subclase: los problemas NP-completos. En esta categoría están los enigmas más difíciles que, además, son equivalentes, es decir, que si se hallase una solución para uno de ellos, significaría que existe una solución para todos los demás.

Actualmente, hay miles de problemas NP-completos en ámbitos muy diversos: biología, física, economía, teoría de números, lógica… Un ejemplo es la forma en que las proteínas adquieren su estructura tridimensional, un problema esencial en biología. Otro es el famoso enigma del viajante: encontrar la ruta más eficiente que debe seguir un repartidor para llegar a todos los destinatarios.

Stephen Cook plantea con esta investigación uno de los grandes Problemas del Milenio, los principales enigmas sin resolver de las matemáticas cuya solución está recompensada con un millón de dólares: ¿existe una solución eficiente para los problemas NP-completos?

Los 45 años de esfuerzos combinados de informáticos y matemáticos no han servido para hallar la solución. La inmensa mayoría de los expertos cree que no hay un algoritmo que resuelva los problemas NP. El Problema del Milenio que planteó Cook se llama P versus NP, es decir, enigmas que tienen solución contra los que no la tienen.

Por ejemplo, en la cuestión del viajante, la única manera de hallar la ruta más rápida para visitar a todos los comerciantes es calcular todas las trayectorias posibles: hay que hacer tantos cálculos que, en la práctica, es irresoluble. El Problema del Milenio planteado por Cook se pregunta si de verdad no existe ninguna manera más rápida, ningún atajo brillante, que permita resolver estos problemas NP-completos.

Si alguien descubriera la fórmula mágica que solucionase un enigma NP-completo, podría solucionarlos todos. Eso comprometería, por ejemplo, los sistemas de encriptado y la seguridad de los bancos e Internet, donde se utilizan problemas NP-completos —que hasta ahora no se pueden resolver— para mantener las claves y las rutas de acceso bajo máxima seguridad.

Stephen Cook es catedrático de Ciencias de la Computación en la Universidad de Toronto (Canadá). Publicó su estudio más influyente en 1971, en el que analizaba e intentaba resolver un problema NP cualquiera. En ese momento no era consciente de cuántos enigmas de ese tipo existían. Solo un año después, otro investigador publicó una lista con 300 problemas NP más. El matemático sabía que el concepto con el que estaba trabajando era interesante, “pero no tenía ni idea de que sería tan importante”, cuenta Cook.

http://tecnologia.elpais.com/tecnologia/2016/01/12/actualidad/1452616109_625533.html