El matemático Stephen Cook, Premio Fundación BBVA por determinar qué pueden resolver los ordenadores con eficiencia

Asimismo, "su trabajo ha tenido un impacto decisivo en todos aquellos campos en los que los cálculos complejos son de vital importancia", según ha dado a conocer este martes el jurado de esta VIII edición de los Premios, que ha anunciado el nombre del galardonado en un acto celebrado en la Fundación BBVA en Madrid.

Estos galardones, creados en 2008 y dotados con 400.000 euros en cada una de las categorías, pretenden reconocer a los autores de avances significativos en distintas áreas científicas, tecnológicas y artísticas, disciplinas que responden al mapa del conocimiento en la última parte del siglo XX y en el presente, así como a retos fundamentales como el cambio climático y la cooperación al desarrollo.

Cook 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", ha explicado.

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. 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]", ha afirmado el matemático.

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.

PRINCIPIO FUNDAMENTAL DE LA CIENCIA DE LA COMPUTACIÓN

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

Así, 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 problema

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.

El jurado de esta categoría está presidido por el catedrático de Ciencias de la Computación de la Universidad de Oxford (Reino Unido), Georg Gottlob, y cuenta como secretario con el director del Instituto de Investigación en Inteligencia Artificial del Consejo Superior de Investigaciones Científicas (CSIC), Ramón López de Mántaras. El resto de los miembros son el director del Laboratorio de Robótica y catedrático de Ciencias de la Computación de la Universidad de Stanford (Estados Unidos), Oussama Khatib; el catedrático de la Facultad de Ciencias de la Computación de la Universidad Otto-von-Guerike-Universität de Magdeburg (Alemania), Rudolf Kruse; el director del Barcelona Supercomputing Center (España), Mateo Valero; y el director de la SCD División del Departamento de Ingeniería Eléctrica de la Universidad Católica de Lovaina (Bélgica), Joos Vandewalle.