Premio Fundación BBVA Fronteras del Conocimiento a Stephen Cook por determinar que hay problemas que los ordenadores no pueden resolver de forma eficiente

Premio Fundación BBVA Fronteras del Conocimiento a Stephen Cook por determinar que hay problemas que los ordenadores no pueden resolver de forma eficiente

• Al concepto de computabilidad de Turing –qué puede resolver o no un ordenador- Cook incorpora la eficiencia, permitiendo prever cuándo merece la pena esforzarse por resolver un problema o solo será viable una aproximación
• Cook define una clase de problemas, los NP-completos, que son los de máxima dificultad y que están vinculados, de modo que si se hallara la solución eficiente a uno de ellos querría decir que todos los demás también la tendrían
• Cook plantea uno de los grandes Problemas del Milenio y es si llegará a haber solución eficiente para los NP-completos, lo que, además, comprometería los actuales sistemas de encriptado y la seguridad que son la base de la economía digital

Madrid, 12 de enero de 2016.-El matemático Stephen Arthur Cook ha sido galardonado con el premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación “por su importante papel a la hora de determinar qué pueden los ordenadores resolver de forma eficiente y qué no”, señala el acta del jurado. Su trabajo “ha tenido un impacto decisivo en todos aquellos campos en los que los cálculos complejos son de vital importancia”.

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.

Sobre los Premios Fundación BBVA Fronteras del Conocimiento

En 2008 la Fundación BBVA creó los premios Fronteras del Conocimiento para reconocer a los autores de avances particularmente significativos en un amplio abanico de á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, áreas todas ellas merecedoras de una mayor visibilidad y reconocimiento social.

Las ocho categorías incluyen áreas clásicas –Ciencias y Biomedicina-; otras más recientes, características de nuestro tiempo –Tecnologías de la Información y la Comunicación, Ecología y Biología de la Conservación, Cambio Climático, Economía, Finanzas y Gestión de Empresas, y Cooperación al Desarrollo; y un área particularmente innovadora de las artes, Música Contemporánea.

Los jurados de cada categoría están compuestos por destacados expertos en sus respectivas áreas. En la organización de los premios la Fundación BBVA cuenta con la colaboración del Consejo Superior de Investigaciones Científicas (CSIC), que designa comisiones técnicas de evaluación que llevan a cabo una primera valoración de las candidaturas y, posteriormente, elevan al jurado una propuesta razonada de finalistas.

En la categoría de TIC los miembros de la comisión técnica del CSIC han sido Juan José García Ripoll, científico titular en el Instituto de Física Fundamental del Consejo Superior de Investigaciones Científicas (IFF-CSIC); Manuel Lozano Fantoba; profesor de investigación y coordinador del área de Ciencia y Tecnologías Físicas en el Instituto de Microelectrónica de Barcelona. Centro Nacional de Microelectónica, del Consejo Superior de Investigaciones Científicas (IMB-CNM-CSIC); Pedro Meseguer González, investigador científico del Instituto de Investigación en Inteligencia Artificial del Consejo Superior de Investigaciones Científicas (IIIA-CSIC); Salvador Miret Artes, profesor de investigación en el Instituto de Física Fundamental del Consejo Superior de Investigaciones Científicas de Madrid (IFT-CSIC) y Carmen Torras Genis, profesora de investigación del Instituto de Robótica e Informática Industrial del Consejo Superior de Investigaciones Científicas (IRII – CSIC).

Jurado de Tecnologías de la Información y la Comunicación

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

Premiados otras ediciones

Puede conocer los galardonados de otros años en el siguiente link:

http://www.fbbva.es/TLFU/tlfu/esp/microsites/premios/fronteras/galardonados/2015/index.jsp

CALENDARIO DE ANUNCIO DE LOS PRÓXIMOS GALARDONADOS

Para más información, póngase en contacto con el Departamento de Comunicación y Relaciones Institucionales de la Fundación BBVA (91 374 52 10, 91 537 37 69, 91 374 81 73 ocomunicacion@fbbva.es) o consultar en la web www.fbbva.es