_
_
_
_

Galardón para el matemático que se rindió frente los ordenadores

Stephen Cook gana el Premio Fronteras del Conocimiento de Tecnologías de la Información

Stephen Cook, premiado con el Fronteras del Conocimiento.
Stephen Cook, premiado con el Fronteras del Conocimiento.FBBVA

Alan Turing describió por primera vez en 1936 el concepto de computabilidad y detalló qué problemas puede resolver o no un ordenador. A esta idea, el matemático Stephen Cook (Nueva York, 1939) añadió la eficiencia: saber si un problema se puede resolver en un tiempo asumible —y el tiempo es la clave— es esencial para decidir si merece la pena insistir en solucionarlo o resignarse y buscar una conclusión aproximada. Con esta idea, el matemático ha ganado el Premio Fronteras del Conocimiento de Tecnologías de la Información, otorgado hoy por la Fundación BBVA.

Más información
Genios entre la inspiración y la locura
Los individuos únicos de la ciencia
Las matemáticas no consiguen resolver un problema de física
Un ordenador supera el Test de Turing simulando tener 13 años
Un algoritmo informático se convierte en el mejor jugador de póquer del mundo

Stephen Cook ha conseguido el galardón por determinar que hay problemas que los ordenadores no pueden resolver de manera eficiente. “En ese caso, lo más inteligente es dejar de intentarlo. Eso permite a los programadores ensayar estrategias mucho más útiles”, explica Cook.

En concreto, el matemático dividió los problemas en dos categorías: los que pueden ser resueltos en un tiempo razonable, a los que llamó P, y aquellos que implicarían tanto tiempo que “el sol se apagaría antes”, a los que llamó NP.

Para estos últimos definió una subclase: los problemas NP-completos. En esta categoría están los enigmas más difíciles que, además, son equivalentes, es decir, que si se hallase una solución para uno de ellos, significaría que existe una solución para todos los demás.

Cook añade la eficiencia a la teoría computacional de Turing, que aclaró qué problemas puede resolver un ordenador y cuáles no

Actualmente, hay miles de problemas NP-completos en ámbitos muy diversos: biología, física, economía, teoría de números, lógica… Un ejemplo es la forma en que las proteínas adquieren su estructura tridimensional, un problema esencial en biología. Otro es el famoso enigma del viajante: encontrar la ruta más eficiente que debe seguir un repartidor para llegar a todos los destinatarios.

Stephen Cook plantea con esta investigación uno de los grandes Problemas del Milenio, los principales enigmas sin resolver de las matemáticas cuya solución está recompensada con un millón de dólares: ¿existe una solución eficiente para los problemas NP-completos?

Los 45 años de esfuerzos combinados de informáticos y matemáticos no han servido para hallar la solución. La inmensa mayoría de los expertos cree que no hay un algoritmo que resuelva los problemas NP. El Problema del Milenio que planteó Cook se llama P versus NP, es decir, enigmas que tienen solución contra los que no la tienen.

Por ejemplo, en la cuestión del viajante, la única manera de hallar la ruta más rápida para visitar a todos los comerciantes es calcular todas las trayectorias posibles: hay que hacer tantos cálculos que, en la práctica, es irresoluble. El Problema del Milenio planteado por Cook se pregunta si de verdad no existe ninguna manera más rápida, ningún atajo brillante, que permita resolver estos problemas NP-completos.

Si alguien resolviera un problema NP-completo, podría resolver todos los que existen

Si alguien descubriera la fórmula mágica que solucionase un enigma NP-completo, podría solucionarlos todos. Eso comprometería, por ejemplo, los sistemas de encriptado y la seguridad de los bancos e Internet, donde se utilizan problemas NP-completos —que hasta ahora no se pueden resolver— para mantener las claves y las rutas de acceso bajo máxima seguridad.

Stephen Cook es catedrático de Ciencias de la Computación en la Universidad de Toronto (Canadá). Publicó su estudio más influyente en 1971, en el que analizaba e intentaba resolver un problema NP cualquiera. En ese momento no era consciente de cuántos enigmas de ese tipo existían. Solo un año después, otro investigador publicó una lista con 300 problemas NP más. El matemático sabía que el concepto con el que estaba trabajando era interesante, “pero no tenía ni idea de que sería tan importante”, cuenta Cook.

Tu suscripción se está usando en otro dispositivo

¿Quieres añadir otro usuario a tu suscripción?

Si continúas leyendo en este dispositivo, no se podrá leer en el otro.

¿Por qué estás viendo esto?

Flecha

Tu suscripción se está usando en otro dispositivo y solo puedes acceder a EL PAÍS desde un dispositivo a la vez.

Si quieres compartir tu cuenta, cambia tu suscripción a la modalidad Premium, así podrás añadir otro usuario. Cada uno accederá con su propia cuenta de email, lo que os permitirá personalizar vuestra experiencia en EL PAÍS.

En el caso de no saber quién está usando tu cuenta, te recomendamos cambiar tu contraseña aquí.

Si decides continuar compartiendo tu cuenta, este mensaje se mostrará en tu dispositivo y en el de la otra persona que está usando tu cuenta de forma indefinida, afectando a tu experiencia de lectura. Puedes consultar aquí los términos y condiciones de la suscripción digital.

Archivado En

Recomendaciones EL PAÍS
Recomendaciones EL PAÍS
Recomendaciones EL PAÍS
_
_