Stephen Cook

Stephen Arthur Cook (nacido el 14 de diciembre de 1939) es un científico informático y matemático estadounidense-canadiense que ha realizado importantes contribuciones a los campos de la teoría de la complejidad y la complejidad de las demostraciones . Es profesor universitario emérito en la Universidad de Toronto , en los departamentos de Ciencias de la Computación y Matemáticas .

Cook es considerado uno de los precursores de la teoría de la complejidad computacional . Ganó el premio Turing de la ACM en 1982 .

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 renovación de su nombramiento. En un discurso que celebraba 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 pudimos 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 a Profesor Distinguido en 1985.

Durante su doctorado, Cook trabajó en la complejidad de las 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 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 booleana (generalmente conocido como SAT) es NP-completo . Este teorema fue demostrado independientemente por Leonid Levin en la Unión Soviética , y por ello 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" plantea si todo problema de optimización cuyas respuestas pueden verificarse eficientemente en cuanto a 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 verificables) 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 , lo 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 figura 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 mención dice lo siguiente:

Por su contribución significativa y profunda a nuestra comprensión de la complejidad de la computación. Su artículo fundamental, « La complejidad de los procedimientos de demostración de teoremas», presentado en el Simposio ACM SIGACT de 1971 sobre la teoría de la computación, sentó las bases de 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 informática durante la última década.

En su artículo «Pruebas constructivas factibles y el 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 utilizando únicamente conceptos de tiempo polinomial. Realizó otra importante contribución al campo en su artículo de 1979, junto con su estudiante Robert A. Reckhow , «La eficiencia relativa de los sistemas de prueba proposicionales» ^{[ 8 ]} , en el que formalizaron las nociones de p-simulación y sistema de prueba proposicional eficiente , lo que dio origen a un área ahora conocida como complejidad de la 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 las cotas inferiores en los sistemas de prueba proposicionales .

Cook recibió una beca conmemorativa NSERC EWR Steacie en 1977, una beca de investigación Killam en 1982 y 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 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 Turing de la ACM 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áximo honor en Ontario . ^{[ 16 ]} Ganó la Medalla de Oro Gerhard Herzberg de Canadá de 2012 para Ciencia e Ingeniería , el máximo honor para científicos e ingenieros en Canadá. ^{[ 17 ]} La Medalla Herzberg es otorgada por el NSERC por "la excelencia sostenida y 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 ] [ 20 ]}

Cook recibió el Premio Fronteras del Conocimiento 2015 de la Fundación BBVA en la categoría de Tecnologías de la Información y la Comunicación "por su importante papel en la identificación de qué problemas pueden y no pueden resolver las computadoras de manera eficiente", según la mención del jurado. Su trabajo, continúa el comunicado, "ha tenido un impacto significativo 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 . ^{[ 21 ]}

• Lista de pioneros en informática

• Página principal de Stephen A. Cook
• 'P versus NP' y los límites de la computación : conferencia pública impartida por Stephen Cook en la Universidad de Toronto.
• Entrevista de historia oral con Stephen Cook en el Instituto Charles Babbage de la Universidad de Minnesota. Cook habló sobre su formación académica en la Universidad de Michigan y la Universidad de Harvard, sus primeros trabajos en la Universidad de California, Berkeley, y su creciente interés en los problemas de complejidad computacional. Cook relató su traslado a la Universidad de Toronto en 1970 y la acogida de su trabajo sobre la NP-completitud, que culminó con la obtención del Premio A. M. Turing.
• Stephen Arthur Cook en el Proyecto de Genealogía Matemática
• Stephen A. Cook en el servidor de bibliografía DBLP