Stephen Arthur Cook OC OOnt (nacido el 14 de diciembre de 1939) es un informático y matemático estadounidense-canadiense que ha realizado importantes contribuciones a los campos de la teoría de la complejidad y la prueba de la complejidad . Es profesor universitario emérito de la Universidad de Toronto , Departamento de Ciencias de la Computación y Departamento de Matemáticas .
Se le considera uno de los antepasados de la teoría de la complejidad computacional .
.jpg/1280px-Stephen_A._Cook_1968_(enlarged_portion).jpg)
Cook recibió su licenciatura en 1961 de la Universidad de Michigan , y su maestría y doctorado de la Universidad de Harvard , respectivamente en 1962 y 1966, del Departamento de Matemáticas. [2] Se unió al departamento de matemáticas de la Universidad de California, Berkeley , en 1966 como profesor asistente, y permaneció allí hasta 1970, cuando se le negó un nuevo nombramiento. En un discurso para celebrar el 30º aniversario del departamento de ingeniería eléctrica y ciencias de la computación de Berkeley, el también ganador del Premio Turing y profesor de Berkeley, Richard Karp , dijo que "es para nuestra eterna vergüenza que no hayamos podido persuadir al departamento de matemáticas para que le otorgara la titularidad. " [3] Cook se unió a la facultad de los Departamentos de Ciencias de la Computación y Matemáticas de la Universidad de Toronto en 1970 como profesor asociado, donde fue ascendido a profesor en 1975 y profesor distinguido en 1985.
Durante su doctorado, Cook trabajó en la complejidad de funciones, principalmente en la multiplicación. En su artículo fundamental de 1971 "La complejidad de los procedimientos de demostración de teoremas", [4] Cook formalizó las nociones de reducción del tiempo polinomial (también conocida como reducción de Cook ) y completitud NP , y demostró la existencia de un problema NP-completo mostrando que el problema de satisfacibilidad booleano (generalmente conocido como SAT) es NP-completo . Este teorema fue demostrado de forma independiente por Leonid Levin en la Unión Soviética , por lo que se le ha dado el nombre de teorema de Cook-Levin . El artículo también formuló el problema más famoso de la informática, el problema P vs. NP . De manera informal, la pregunta "P vs. NP" pregunta si cada problema de optimización cuyas respuestas se pueden verificar de manera eficiente en cuanto a corrección/optimidad se puede resolver de manera óptima con un algoritmo eficiente. Dada la abundancia de este tipo de problemas de optimización en la vida cotidiana, una respuesta positiva a la pregunta "P versus NP" probablemente tendría profundas consecuencias prácticas y filosóficas.
Cook conjetura que existen problemas de optimización (con soluciones fácilmente comprobables) que no pueden resolverse mediante algoritmos eficientes, es decir, P no es igual a NP. Esta conjetura ha generado una gran cantidad de investigaciones en teoría de la complejidad computacional , que ha mejorado considerablemente nuestra comprensión de la dificultad inherente de los problemas computacionales y de lo que se puede calcular de manera eficiente. Sin embargo, la conjetura sigue abierta y se encuentra entre los siete famosos Problemas del Premio del Milenio . [5] [6]
En 1982, Cook recibió el Premio Turing por sus contribuciones a la teoría de la complejidad. Su cita dice:
Por su avance en nuestra comprensión de la complejidad de la computación de una manera significativa y profunda. Su artículo fundamental, La complejidad de los procedimientos de demostración de teoremas, presentado en el Simposio ACM SIGACT sobre Teoría de la Computación de 1971, sentó las bases para la teoría de la NP-Completitud. La consiguiente exploración de los límites y la naturaleza de la clase de problemas NP-completos ha sido una de las actividades de investigación más activas e importantes en informática durante la última década.
En su artículo "Feasfully Constructive Proofs and the Propositional Calculus" [7] publicado en 1975, introdujo la teoría ecuacional PV (que significa Polynomial-time Verifiable) para formalizar la noción de pruebas utilizando únicamente conceptos de tiempo polinomial. Hizo otra contribución importante al campo en su artículo de 1979, junto con su alumno Robert A. Reckhow, "The Relative Efficiency of Propositional Proof Systems", [8] en el que formalizaron las nociones de p-simulación y sistema de prueba proposicional eficiente. , que inició un área ahora llamada complejidad de prueba proposicional . Demostraron que la existencia de un sistema de prueba en el que cada fórmula verdadera tiene una prueba corta es equivalente a NP = coNP . Cook fue coautor de un libro con su alumno Phuong The Nguyen en esta área titulado "Fundamentos lógicos de la complejidad de la prueba". [9]
Sus principales áreas de investigación son la teoría de la complejidad y la complejidad de la prueba , con incursiones en la semántica de los lenguajes de programación , la computación paralela y la inteligencia artificial . Otras áreas en las que ha contribuido incluyen aritmética acotada , matemáticas inversas acotadas , complejidad de funciones de tipo superior, complejidad del análisis y límites inferiores en sistemas de prueba proposicionales .
Llamó a la clase de complejidad NC en honor a Nick Pippenger . La clase de complejidad SC lleva su nombre. [10] También introduce la definición de la clase de complejidad AC 0 y su jerarquía AC . [11]
Según Don Knuth, el algoritmo KMP se inspiró en los autómatas de Cook para reconocer palíndromos concatenados en tiempo lineal . [12]
Cook recibió una beca NSERC EWR Steacie Memorial en 1977, una beca de investigación Killam en 1982 y recibió el premio CRM-Fields-PIMS en 1999. Ha ganado el premio John L. Synge y la medalla Bernard Bolzano de la Academia Checa de Ciencias ( 2008), [13] y es miembro de la Royal Society de Londres y de la Royal Society de Canadá . Cook fue elegido miembro de la Academia Nacional de Ciencias (Estados Unidos) y de la Academia Estadounidense de Artes y Ciencias . Es miembro correspondiente de la Academia de Ciencias y Humanidades de Gotinga .
Cook ganó el premio ACM Turing en 1982. La Association for Computing Machinery lo honró como miembro de ACM en 2008 por sus contribuciones fundamentales a la teoría de la complejidad computacional . [14] Fue seleccionado por la Asociación de Lógica Simbólica para dar la Conferencia Gödel en 1999. [15]
El Gobierno de Ontario lo nombró miembro de la Orden de Ontario en 2013, el más alto honor en Ontario . [16] Ganó la Medalla de Oro Gerhard Herzberg de Canadá en Ciencias e Ingeniería 2012 , el más alto honor para científicos e ingenieros en Canadá. [17] La Medalla Herzberg es otorgada por NSERC por "tanto la excelencia sostenida como la influencia general del trabajo de investigación realizado en Canadá en ciencias naturales o ingeniería". [18] Fue nombrado Oficial de la Orden de Canadá en 2015. [19]
Cook recibió el Premio Fundación BBVA Fronteras del Conocimiento 2015 en la categoría de Tecnologías de la Información y las Comunicaciones "por su importante papel a la hora de identificar lo que los ordenadores pueden y no pueden resolver de manera eficiente", según palabras del mención del jurado. Su trabajo, continúa, "ha tenido un impacto dramático en todos los campos donde los cálculos complejos son cruciales".
Cook ha supervisado a numerosos estudiantes de maestría y 36 estudiantes de doctorado han completado sus títulos bajo su supervisión. [1]
Cook vive con su esposa en Toronto . Tienen dos hijos, uno de los cuales es el regatista olímpico Gordon Cook . [20]
