Galard¨®n para el matem¨¢tico que se rindi¨® frente los ordenadores

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.

Cook a?ade la eficiencia a la teor¨ªa computacional de Turing, que aclar¨® qu¨¦ problemas puede resolver un ordenador y cu¨¢les no

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 resolviera un problema NP-completo, podr¨ªa resolver todos los que existen

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.