Esteban Cook

Stephen Arthur Cook OC OOnt (nacido el 14 de diciembre de 1939) es un informático y matemático estadounidense-canadiense que ha realizado contribuciones significativas a los campos de la teoría de la complejidad y la complejidad de las pruebas. Es profesor universitario en la Universidad de Toronto, Departamento de Ciencias de la Computación y Departamento de Matemáticas.

Biografía

Cocinar en 1968

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. 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 para celebrar 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: "Es para nuestra vergüenza eterna que no pudimos persuadir al departamento de matemáticas para que diera él tenencia." 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.

Investigación

Stephen Cook es considerado uno de los precursores de la teoría de la complejidad computacional.

Durante su doctorado, Cook trabajó en la complejidad de las funciones, principalmente en la multiplicación. En su artículo seminal de 1971 'La complejidad de los procedimientos de prueba de teoremas', Cook formalizó las nociones de reducción de tiempo polinomial (también conocida como reducción de Cook) y NP-completo, 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 y, por lo tanto, se le ha dado el nombre de teorema de Cook-Levin. El documento también formuló el problema más famoso en informática, el problema P vs. NP. De manera informal, el "P vs. NP" La pregunta pregunta si cada problema de optimización cuyas respuestas se pueden verificar de manera eficiente para la corrección/optimidad se puede resolver 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" La pregunta 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, 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 permanece abierta y se encuentra entre los siete famosos Problemas del Premio del Milenio.

En 1982, Cook recibió el Premio Turing por sus contribuciones a la teoría de la complejidad. Su cita dice:

Para su avance en nuestra comprensión de la complejidad de la computación de una manera significativa y profunda. Su papel seminal, Complejidad de los procedimientos de prueba de teoremas, presentado en el Simposio ACM SIGACT sobre la Teoría de la Computación de 1971, sentó las bases para la teoría de la Completeidad NP. La exploración posterior de los límites y la naturaleza de la clase completa de problemas de NP ha sido una de las actividades de investigación más activas e importantes en la informática durante el último decenio.

En su "Pruebas factiblemente constructivas y el cálculo proposicional" En un artículo publicado en 1975, introdujo la teoría ecuacional PV (que significa Polynomial-time Verifiable) para formalizar la noción de pruebas utilizando solo conceptos de tiempo polinomial. Hizo otra contribución importante al campo en su artículo de 1979, junto con su alumno Robert A. Reckhow, 'La eficiencia relativa de los sistemas de prueba proposicional', en el que formalizaron las nociones de p-simulación y proposición eficiente. sistema de prueba, 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 es coautor de un libro con su estudiante Phuong The Nguyen en esta área titulado "Fundamentos lógicos de la complejidad de la prueba".

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 del lenguaje 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 de análisis y límites inferiores en sistemas de prueba proposicional.

Algunas otras contribuciones

Llamó a la clase de complejidad NC en honor a Nick Pippenger. La clase de complejidad SC lleva su nombre. También introduce la definición de la clase de complejidad AC0 y su jerarquía AC.

Según Don Knuth, el algoritmo KMP se inspiró en los autómatas de Cook para reconocer palíndromos concatenados en tiempo lineal.

Premios y distinciones

Cook recibió un premio NSERC E.W.R. Steacie Memorial Fellowship en 1977, Killam Research Fellowship en 1982 y recibió el premio CRM-Fields-PIMS en 1999. Ha ganado el premio John L. Synge y la medalla Bernard Bolzano, y es miembro de la Royal Society of London y Royal Sociedad de Canadá. Cook fue elegido miembro de la Academia Nacional de Ciencias (Estados Unidos) y la Academia Estadounidense de las Artes y las Ciencias.

Cook ganó el premio ACM Turing en 1982. Association for Computing Machinery lo honró como miembro de ACM en 2008 por su Contribuciones fundamentales a la teoría de la complejidad computacional. Fue seleccionado por la Association for Symbolic Logic para dar la Gödel Lecture en 1999.

El Gobierno de Ontario lo nombró miembro de la Orden de Ontario en 2013, el mayor honor en Ontario. Ha ganado la Medalla de Oro Gerhard Herzberg Canada 2012 para Ciencias e Ingeniería, el más alto honor para científicos e ingenieros en Canadá. La Medalla Herzberg es otorgada por NSERC por "la excelencia sostenida y la influencia general del trabajo de investigación realizado en Canadá en ciencias naturales o ingeniería". Fue nombrado Oficial de la Orden de Canadá en 2015.

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 las computadoras pueden y no pueden resolver de manera eficiente" en palabras de la citació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.

Vida privada

Cook vive con su esposa en Toronto. Tienen dos hijos, Gordon y James. Toca el violín y le gusta navegar. A menudo se le llama por su nombre corto Steve Cook.