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. 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.
Discurso
Tecnologías de la Información y la Comunicación VIII edición
El hoy problema más famoso en ciencias de la computación, sobre cuya cabeza pesa una recompensa de un millón de dólares, nació como un enigma matemático más. Atractivo e interesante, sin duda, pero humilde. Ni siquiera su descubridor, el matemático estadounidense Stephen Cook, advirtió al principio sus muchas implicaciones. Se trata del problema P versus NP, que se ocupa de lo que puede resolver una computadora de forma eficiente.
Cook lo formuló en 1971. La era de los ordenadores estaba entonces en sus inicios y el valor de la aportación de Cook no era fácilmente apreciable. Sin embargo, solo un año después otro matemático publicó una lista con decenas de problemas que en la práctica, y según el estado de conocimiento actual, quedan fuera del alcance de las computadoras. Eran muchos más de los esperados. Fue el comienzo de la fama de P versus NP, y de Stephen Cook.
Con los años la lista de problemas irresolubles en tiempo asumible ha seguido creciendo y P versus NP se ha convertido en una espada Excálibur a la que todo genio matemático se ha enfrentado alguna vez. En cuanto a Stephen A. Cook, hoy es catedrático de Ciencias de la Computación en la Universidad de Toronto y el ganador del Premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación “por su trabajo pionero de enorme influencia en complejidad computacional”.
De niño Cook no conocía a ningún matemático, no sabía “lo que hacían realmente” —ha comentado en alguna ocasión—, pero en cambio sí tenía la experiencia de haber trabajado un verano siendo adolescente con el inventor del marcapasos cardiaco implantable, Wilson Greatbach, quien vivía en su misma ciudad. Eso, unido a su interés por los transistores que empezaban a llegar al mercado, le hizo matricularse en Ingeniería en la Universidad de Míchigan. Un profesor que advirtió sus habilidades le ganó para las matemáticas.
Tras doctorarse en Harvard en 1966, comenzó su relación con las ciencias de la computación, un área que los matemáticos, en palabras del propio Cook, “aún no consideraban del todo respetable matemáticamente”. Quizás por eso el Departamento de Matemáticas de la Universidad de California en Berkeley, donde Cook fue profesor cuatro años, no le ofreció un puesto estable. Richard Karp, del Departamento de Ciencias de la Computación en Berkeley, ha escrito: “Será siempre motivo de vergüenza para nosotros el no haber logrado convencer al Departamento de Matemáticas [de ofrecer una plaza a Cook]”.
En 1970 Cook aceptó una oferta de la Universidad de Toronto. En esa época “los ordenadores eran relativamente nuevos y parecía muy natural estudiar qué problemas pueden resolver de forma eficiente”, dice Cook para explicar por qué escogió su área de investigación. La cuestión de la eficiencia es importante. Alan Turing ya había definido décadas atrás qué pueden resolver los ordenadores y qué no en términos absolutos.
Pero sucede que «hay problemas que sí pueden ser resueltos por un ordenador, solo que la máquina tardaría tanto que el Sol moriría antes», señala Cook. Estos problemas en la práctica irresolubles se dan en biología, física, economía… y es interesante identificarlos para no “desperdiciar esfuerzo» intentando resolverlos y concentrarse, en cambio, en la búsqueda de «soluciones aproximadas pero útiles”, señala Cook. Hoy día no cabe ya duda de la admiración que matemáticos y expertos en computación sienten por el padre de P versus NP, uno de los siete problemas del milenio, cuya resolución premia con un millón de dólares el Clay Mathematics Institute (Estados Unidos). NP —por sus siglas en inglés de tiempo no determinista polinomial— son los problemas que no pueden ser resueltos eficientemente, y P los que sí.
Un ejemplo de problema NP es el conocido como del viajante: se trata de hallar la ruta más corta para un repartidor que debe entregar muchos paquetes. En los problemas NP solo se encuentra la respuesta correcta probando todas las opciones, algo que puede llevar miles de millones de años incluso al ordenador más potente. Ahora bien, ¿seguro que no existe un algoritmo que dé una solución evitando hacer todos esos cálculos? ¿De verdad no hay un atajo brillante para resolver los problemas NP? Justamente eso es lo que plantea el problema P versus NP.
A fecha de hoy, la respuesta es un rotundo “no se sabe”. Es posible que los NP sean, en realidad, problemas P disfrazados, problemas solubles eficientemente pero para los que nadie ha encontrado todavía el método de ataque adecuado. La gran aportación de Cook fue determinar que dentro de la clase NP hay una subclase que denominó NP completa. Los NP completos son problemas llave, porque si se encuentra una manera de resolver eficientemente solo uno de ellos, significa que todos —todos los NP— pueden resolverse eficientemente.
A la inversa, si se demostrara que realmente no existe método capaz de resolver un NP completo en tiempo asumible, la barrera entre P y NP quedaría blindada para siempre. Cook apuesta por la última opción. Esa es su conjetura: que P y NP son distintos. A él lo que más le gusta de las matemáticas es “la idea de que puedes probar que una proposición precisa es verdadera sin que ningún argumento racional pueda poner en duda ese hecho”. Pero no le queda más remedio, por ahora, que aceptar que la conjetura de Cook viva en el limbo de lo que todavía no ha podido ser demostrado.
