Premio Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación
La Fundación BBVA reconoce la labor del matemático por determinar que hay problemas que los ordenadores no pueden resolver de forma eficiente
El matemático Stephen Arthur Cook (Buffalo, Nueva York, 1939) ha sido galardonado con el premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación "por su importante papel a la hora de determinar qué pueden los ordenadores resolver de forma eficiente y qué no", señala el acta del jurado. Su trabajo "ha tenido un impacto decisivo en todos aquellos campos en los que los cálculos complejos son de vital importancia".
Saber si un problema es soluble o no en un tiempo asumible es esencial para decidir cómo enfrentarse a él. Stephen Cook descubrió una clase específica de problemas, llamada 'NP-completos', tal que -como él mismo ha explicado por teléfono tras recibir la noticia del premio- "si puedes demostrar que un problema es NP-completo, entonces lo que deberías hacer es simplemente dejar de intentar resolverlo".
Esta sabiduría a la hora de decidir cuándo rendirse parecería una derrota, pero desde el punto de vista de las aplicaciones prácticas resulta ser todo lo contrario: en vez de desperdiciar esfuerzos persiguiendo un imposible, los programadores ensayan estrategias "mucho más útiles -dice Cook- por ejemplo buscar soluciones aproximadas".
Cook es catedrático de Ciencias de la Computación en la Universidad de Toronto. Su nominación defiende que su aportación es, junto al concepto de "computabilidad" de Alan Turing, uno de los hitos en la fundamentación 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.
"Hay problemas que en principio pueden ser resueltos por un ordenador, pero la máquina tardaría tanto que el sol moriría antes -prosigue Cook-. Esos son los problemas que llamamos NP. Y están los problemas que llamamos P, que sí pueden ser resueltos en un tiempo razonable. La cuestión es decidir qué problemas son NP [no solubles eficientemente], y cuáles son P [fácilmente solubles]".
La principal aportación de Cook fue determinar que dentro de la clase NP, había una subclase que denominó NP completa, y cuyo rasgos distintivos son que, además de ser los más difíciles, son computacionalmente equivalentes; es decir, si se hallara un algoritmo eficiente para uno de ellos, significaría que existe un algoritmo para el resto y no solo de los NP completos, sino para el conjunto de los NP.
Los problemas y sus usos
Como afirma el acta del jurado, "el concepto de 'NP-completo' se considera uno de los principios fundamentales de la ciencia de la computación". Hoy se conocen literalmente 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.
La definición de los problemas NP-completos proporciona importantes directrices para los científicos e ingenieros, y también para los técnicos informáticos, que deben diseñar los algoritmos con que hacer frente a los problemas.
Cook publicó su paper más influyente en 1971, poco después de doctorarse. Partió de un determinado problema NP, y entonces no imaginaba cuántos problemas de ese tipo existían. Sabía que el concepto con el que trabajaba era "interesante" -dijo ayer-, pero no sospechaba que acabaría siendo tan importante. Solo un año después de la publicación de su trabajo otro matemático publicó una lista con unos trescientos problemas NP, es decir, problemas que los ordenadores no pueden resolver de forma eficiente.
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 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.
Cook se ha mostrado "muy sorprendido" y "encantado" con el premio. A lo largo de su carrera ha sido testigo de "cómo las ciencias de la computación evolucionaban de forma impresionante", algo que le fascina.