El fallo del jurado se hizo público este martes en un acto celebrado en Madrid al que no pudo asistir Artur Cook, que intervino por teléfono y agradeció la concesión del galardón. De acuerdo con el acta, el trabajo de Cook “ha tenido un impacto decisivo en todos aquellos campos en los que los cálculos complejos son de vital importancia”.

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” afirmó Cook. “A este tipo de problemas los llamamos NP (no deterministas en tiempo polinómico) mientras que los problemas que llamamos P sí pueden ser resueltos en un tiempo razonable”.

La aportación de Cook se basa en 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.

El trabajo de Cook dio lugar al problema de ‘P versus NP’, el cual es uno de los siete problemas incluidos en la lista de ‘Problemas del Milenio’ del Clay Mathematics Institute de Estados Unidos cuya resolución se premia con un millón de dólares. El problema pregunta si de verdad no existe ninguna otra manera más rápida, ningún atajo brillante, que permita resolver los problemas NP.