fbbva-15-tic-stephen-arthur-cook

Stephen Arthur Cook

PREMIO FRONTERAS DEL CONOCIMIENTO

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

VIII Edición

El premio se le ha concedido a Stephen Cook por su importante papel a la hora de determinar qué pueden los ordenadores resolver de forma 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.

MENCIÓN DEL ACTA

El Premio Fundación BBVA Fronteras del Conocimiento en Tecnologías de la Información y la Comunicación, en su octava edición, ha sido concedido a Stephen A. Cook por el carácter pionero y la enorme influencia de sus trabajos sobre complejidad computacional. El trabajo de Stephen A. Cook juega un papel importante a la hora de determinar qué es lo que pueden los ordenadores resolver y qué no de forma eficiente.

Su concepto de NP completo se considera uno de los principios fundamentales de la ciencia de la computación. En su obra seminal de 1971, ‘La complejidad de los procedimientos de demostración de teoremas’, Cook otorgó un significado matemático a la expresión “eficientemente calculable”: un problema es eficientemente calculable si pertenece a la clase P de problemas calculables en un tiempo polinómico determinista. También atribuyó un significado matemático a la expresión “eficientemente verificable”, en un tiempo polinómico, una vez se ha hallado una solución.

Un problema eficientemente verificable, si tiene solución, se puede resolver por el método de tanteo y error. El primer paso consiste en conjeturar una propuesta de solución (la denominada conjetura no determinista) para a continuación verificar eficientemente que esa conjetura es de hecho una solución (la conjetura determinista en tiempo polinómico). Por esta razón, esa clase de problemas se denomina NP para tiempo polinómico no determinista.

Cook estableció el conocido problema de P versus NP, que cuestiona si todo problema de decisión que sea eficientemente verificable (en NP) puede hacerse eficientemente calculable (en P) y conjeturarse (la conocida actualmente como hipótesis de Cook) que P ≠ NP. La cuestión de P versus NP es en la actualidad uno de los siete problemas del milenio.

Stephen Cook demostró que hay problemas concretos de la clase NP en los que pueden transformarse eficientemente todos los demás problemas del conjunto NP. Estos problemas se denominan problemas NP completo. Si un problema NP completo se puede resolver en tiempo polinómico, entonces todos se pueden resolver. Hoy se conocen miles de problemas NP completo en ámbitos tan diversos como la biología, física o economía.