Stephen Cook, el matemático premiado por «rendirse» ante un ordenador

Saber cuándo tirar la toalla también tiene mérito, y mucho. Incluso puede suponer un auténtico triunfo. 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 precisamente por ello, por definir qué no merece la pena pedirle a un ordenador. Este científico de 76 años, catedrático de Ciencias de la Computación en la Universidad de Toronto, ha ayudado a determinar qué pueden resolver los ordenadores de manera eficiente y qué no. Su trabajo ha tenido «un impacto decisivo en todos aquellos campos en los que los cálculos complejos son de vital importancia», según el fallo del jurado dado a conocer este martes.

En concreto, lo que Cook descubrió es una clase específica de problemas, llamada NP-completos. En sus propias palabras, si se da con uno de ellos, «lo que deberías hacer es simplemente dejar de intentar resolverlo». No es una derrota, sino todo lo contrario. Tener este conocimiento permite a los programadores ensayar estrategias «mucho más útiles, como por ejemplo buscar soluciones aproximadas».

La nominación de Cook defiende que su aportación es, junto al concepto de «computabilidad» de Turing, uno de los hitos en los fundamentos matemáticos de la computación. El genio británico especificó en su día qué pueden resolver los ordenadores y qué no, a lo que Cook ha incorporado el principio de eficiencia para determinar qué pueden resolver, sí, pero de forma eficiente.

«Hay problemas que en principio pueden ser resueltos por un ordenador, pero la máquina tardaría tanto que el Sol moriría antes», dice el matemático en un comunicado dado a conocer por la Fundación BBVA. Esos son los problemas NP. Por el contrario, los problemas P son los que pueden ser resueltos en un tiempo razonable. La cuestión es decidir a qué grupo pertenece cada problema. Además, la principal aportación de Cook fue determinar que dentro de la clase NP había una subclase que denominó NP completa, que son los más difíciles y computacionalmente equivalentes; es decir, si se hallara un algoritmo eficiente para uno de ellos, significaría que existe uno para el resto, para el conjunto de los NP.

Problema del viajante

Hoy en día se conocen miles de problemas NP completos en biología, física, economía, teoría de los números, lógica... como la forma en la que las proteínas adquieren su estructura tridimensional, o como el problema del viajante: hallar la ruta más eficiente que debe seguir un repartidor para llegar a muchos destinatarios. El trabajo de Cook también ha dado lugar a uno de los principales problemas sin resolver de las matemáticas, el problema de P versus NP. Es uno de los siete Problemas del Milenio del Clay Mathematics Institute (EE.UU.), cuya resolución se premia con un millón de dólares.

Este problema se pregunta si de verdad no hay ninguna otra manera más rápida, ningún atajo brillante, que permita resolver los problemas NP. Hoy, la mayoría de los matemáticos cree que no existe ningún algoritmo así, y que por tanto los problemas NP son realmente irresolubles. Eso sí, nadie lo ha demostrado y Cook no cree que nadie sea capaz a corto plazo. Si se encontrara, las implicaciones serían gigantescas, ya que comprometería el sistema de encriptado y seguridad que son la base de la economía digital.

Lee la entrevista con Leonard Kleinrock, ganador de la edición de 2015: «Los ordenadores son el peor enemigo del pensamiento crítico».