Stephen Arthur Cook OC OOnt (nacido el 14 de diciembre de 1939) es un informático y matemático estadounidense-canadiense que ha hecho importantes contribuciones en los campos de la teoría de la complejidad y la complejidad de las pruebas . Es profesor universitario emérito en la Universidad de Toronto , Departamento de Ciencias de la Computación y Departamento de Matemáticas .
Se le considera uno de los precursores 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ó la reelección. En un discurso celebrando el 30 aniversario del departamento de ingeniería eléctrica y ciencias de la computación de Berkeley, el 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 diera 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 influyente artículo de 1971 "La complejidad de los procedimientos de demostración de teoremas", [4] Cook formalizó las nociones de reducción en tiempo polinomial (también conocida como reducción de Cook ) y NP-completitud , y demostró la existencia de un problema NP-completo al mostrar 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 , y por lo tanto se le ha dado el nombre de teorema de Cook-Levin . El artículo también formuló el problema más famoso en informática, el problema P vs. NP . De manera informal, la pregunta "P vs. NP" pregunta si cada problema de optimización cuyas respuestas pueden verificarse eficientemente para su corrección/optimalidad puede resolverse de manera óptima con un algoritmo eficiente. Dada la abundancia de tales problemas de optimización en la vida cotidiana, una respuesta positiva a la pregunta "P vs. 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 investigación en la 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 permanece 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 seminal, The Complexity of Theorem Proving Procedures, presentado en el Simposio ACM SIGACT de 1971 sobre la teoría de la computación, sentó las bases para la teoría de la NP-Completitud. La exploración subsiguiente 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 la ciencia de la computación durante la última década.
En su artículo "Pruebas factiblemente constructivas y cálculo proposicional" [7] publicado en 1975, introdujo la teoría ecuacional PV (que significa verificable en tiempo polinomial) para formalizar la noción de pruebas que utilizan únicamente conceptos de tiempo polinomial. Hizo otra contribución importante al campo en su artículo de 1979, junto con su estudiante Robert A. Reckhow, "La eficiencia relativa de los sistemas de prueba proposicional", [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 estudiante 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 las pruebas , con incursiones en la semántica de los lenguajes de programación , la computación paralela y la inteligencia artificial . Otras áreas a las que ha contribuido incluyen la aritmética acotada , las matemáticas inversas acotadas , la complejidad de las funciones de tipo superior, la complejidad del análisis y los límites inferiores en los sistemas de prueba proposicionales .
La clase de complejidad NC fue nombrada en honor a Nick Pippenger . La clase de complejidad SC lleva su nombre. [10] La definición de la clase de complejidad AC 0 y su jerarquía AC también fueron introducidas por él. [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 of London y la Royal Society of Canada . 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 Göttingen .
Cook ganó el premio ACM Turing en 1982. La Association for Computing Machinery lo honró como miembro de la ACM en 2008 por sus contribuciones fundamentales a la teoría de la complejidad computacional . [14] Fue seleccionado por la Association for Symbolic Logic 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] Ha ganado la Medalla de Oro Gerhard Herzberg de Canadá en 2012 para Ciencias e Ingeniería , 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 las ciencias naturales o la 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 la Comunicación "por su importante papel en la identificación de lo que los ordenadores pueden y no pueden resolver de manera eficiente", según el acta del jurado. Su trabajo, continúa, "ha tenido un impacto dramático en todos los campos en los que 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]
