Stephen Arthur Cook, premio Fronteras del Conocimiento en tecnologías de la información

El matemático Stephen Arthur Cook 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 (TIC). El jurado ha valorado "su importante papel a la hora de determinar qué pueden los ordenadores resolver de forma eficiente y qué no”.

Saber si un problema es soluble o no en un tiempo asumible es esencial para decidir cómo enfrentarse a él. El matemático neoyorkino descubrió una clase específica de problemas, llamada NP-completos. "Si puedes demostrar que un problema es NP-completo, entonces lo que deberías hacer es simplemente dejar de intentar resolverlo”, señaló ayer durante una conversación telefónica en la que se le comunicó el premio.

Esta sabiduría a la hora de decidir cuándo rendirse podría parecer 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”.

Principio de eficiencia

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", destaca el acta del jurado.

“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.

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.

Lista de problemas 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 versus NP. Es uno de los siete problemas incluidos en la lista de Problemas del Milenio del Clay Mathematics Institute (EEUU), cuya resolución se premia con un millón de dólares.

En términos no técnicos, 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 los problemas NP. 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.

Hoy 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. Es decir, P y NP son problemas de verdad distintos en complejidad. Pero nadie lo ha demostrado, y “no creo que nadie lo vaya a hacer a corto plazo”, dce Cook.

La clase de problemas que él descubrió, los NP-completos, son en cierto modo problemas ‘llave’, porque son un tipo específico de problemas NP que, si se demuestra que existe un algoritmo que los resuelva, “entonces todos los problemas NP podrían resolverse fácilmente”, explica Cook, “y eso implica que las dos clases P y NP coincidirían”. Bastaría con resolver un único problema NP completo para demostrar que ningún NP es irresoluble. Pero Cook insiste: “Nosotros creemos que P y NP son distintos, y que NP son realmente difíciles”.

Como explica el acta, 45 años de esfuerzos combinados de informáticos y matemáticos no han servido para hallar un algoritmo eficiente para los problemas NP-completos.

Si se encontrara ese algoritmo, las implicaciones serían enormes, porque comprometería el sistema de encriptado –fundamentado en problemas NP- y la seguridad que son la base de la economía digital.

Cook se mostró ayer “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.