Saber si un problema es soluble o no en un tiempo asumible es esencial para decidir cómo enfrentarse a él. Stephen Cook descubrió una clase específica de problemas, llamada NP-completos, tal que -como él mismo explicó ayer por teléfono tras recibir la noticia del premio- “si puedes demostrar que un problema es NP-completo, entonces lo que deberías hacer es simplemente dejar de  intentar resolverlo”.

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

Problema 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 (EE.UU.), 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”, dijo ayer 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.

Biografía

Stephen Arthur Cook (Buffalo, Nueva York, Estados Unidos, 1939) ostenta la doble nacionalidad estadounidense y canadiense. Hijo de un químico y un ama de casa con dos máster (en Inglés y en Historia), su primera vocación fue la ciencia aplicada. De hecho, mientras cursaba secundaria ayudó a Wilson Greatbatch, el inventor del primer marcapasos cardiaco implantable, a soldar circuitos en los primeros prototipos del dispositivo.

Cuando se matriculó en la Universidad de Michigan -donde sus padres se habían conocido- optó por Ciencias de la Ingeniería, pero destacó tanto en las asignaturas de Matemáticas que acabó dando el salto a esta carrera y obtuvo la licenciatura en 1961.

Tras hacer los estudios de máster fue a Harvard a hacer el doctorado. En aquel momento no estaba especialmente interesado en la computación. Como él mismo afirma: “Ni siquiera sabía realmente lo que quería hacer; puse Álgebra como mi área”. Pero allí descubrió, entre otros, los papers de Alan Cobham sobre complejidad computacional y acabó haciendo la tesis doctoral en este campo, en concreto sobre la complejidad de la multiplicación.

A continuación se incorporó al Departamento de Matemáticas de la Universidad de Berkeley, donde estuvo cuatro años. De ahí marchó, en 1970, al Departamento de Ciencia de la Computación de la Universidad de Toronto, donde continúa siendo catedrático. Un año más tarde hizo su aportación seminal en el paper “The complexity of Theorem Proving Procedures”, que presentó en el congreso del Special Interest Group on Algorithms and Computational Theory de la Association for Computing Machinery.