(EFE).- El matemático estadounidense Stephen Arthur Cook ha sido galardonado con el premio Fronteras del Conocimiento de la Fundación BBVA en la categoría de Tecnologías de la Información y Comunicación por contribuir a definir qué problemas no pueden resolver los ordenadores de manera eficiente y cuáles sí.
Estas investigaciones han tenido “un impacto decisivo en todos aquellos campos en los que los cálculos complejos son de vital importancia”, según el fallo dado a conocer hoy de un premio dotado con 400.000 euros (436.000 dólares).
El trabajo de Cook, de 76 años y catedrático de Ciencias de la Computación en la Universidad de Toronto, ha sido señalado, junto al concepto de computabilidad de Alan Turing, como uno de los hitos en la fundamentación matemática de la computación.
“La teoría de Turing definió la complejidad, mi contribución fue la introducción de la clase NP-Completa. Yo sólo intento probar que hay problemas que un ordenador no va a resolver eficazmente, así que no pierdas tu tiempo intentando resolver algo irresoluble, busca soluciones aproximadas”, afirmó el matemático en un contacto telefónico establecido durante la rueda de prensa para anunciar el ganador.
Según Cook, 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 llamados NP. Y están los denominados P, los 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)”, explicó.
La principal aportación de Cook fue determinar que dentro de la clase NP hay una subclase -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.
Cook insistió en que existen problemas -los NP completos, no solubles eficientemente- que “podrían tardar miles de años en resolverse”, algo que según destaca el jurado no se había podido probar.
Para el presidente del jurado, Georg Gottlob, se trata de “una contribución decisiva” y “una aportación importante en la vida cotidiana“, ya que “en todas partes hay problemas NP-completos que resolver”.
El trabajo de Cook -publicado en 1971, poco después de doctorarse- dio lugar al que hoy es considerado uno de los principales problemas sin resolver de las matemáticas, uno de los siete “Problemas del Milenio” del Clay Mathematics Institute, señaló Gottlob.
Cuarenta y cinco años de esfuerzos no han servido para hallar un algoritmo eficiente para los problemas NP completos y, de encontrarse, el sistema de encriptado y la seguridad -bases de la economía digital- se verían comprometidos, según advierten los expertos.
En la actualidad se conocen 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.
Solo un año después de la publicación del trabajo de Cook, otro matemático publicó una lista con unos trescientos problemas NP completos.
