Hispanopedia Wiki
Articulo de referencia

Stephen Cook

[[University of California, Berkeley]]"},"education":{"wt":"[[University of Michigan]] ([[Bachelor of Arts|BA]]) [[Harvard University]] ([[Master of Arts|MA]], [[Doctor of Philo...

Hispanopedia WikiContenido en espanolLectura gratuita

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 .

Biografía

Cook 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. [ 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.

Investigación

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 .

Otras contribuciones

Él nombró la clase de complejidad NC 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 ]

Premios y distinciones

Cook was awarded an NSERC E.W.R. Steacie Memorial Fellowship in 1977, a Killam Research Fellowship in 1982, and received the CRM-Fields-PIMS prize in 1999. He has won John L. Synge Award and Bernard Bolzano Medal of the Czech Academy of Sciences (2008),[13] and is a fellow of the Royal Society of London and Royal Society of Canada. Cook was elected to membership in the National Academy of Sciences (United States) and the American Academy of Arts and Sciences. He is a corresponding member of the Göttingen Academy of Sciences and Humanities.

Cook won the ACM Turing Award in 1982. Association for Computing Machinery honored him as a Fellow of ACM in 2008 for his fundamental contributions to the theory of computational complexity.[14] He was selected by the Association for Symbolic Logic to give the Gödel Lecture in 1999.[15]

The Government of Ontario appointed him to the Order of Ontario in 2013, the highest honor in Ontario.[16] He has won the 2012 Gerhard Herzberg Canada Gold Medal for Science and Engineering, the highest honor for scientists and engineers in Canada.[17] The Herzberg Medal is awarded by NSERC for "both the sustained excellence and overall influence of research work conducted in Canada in the natural sciences or engineering".[18] He was named an Officer of the Order of Canada in 2015.[19][20]

Cook was granted the BBVA Foundation Frontiers of Knowledge Award 2015 in the Information and Communication Technologies category "for his important role in identifying what computers can and cannot solve efficiently," in the words of the jury's citation. His work, it continues, "has had a dramatic impact in all fields where complex computations are crucial."

Cook has supervised numerous MSc students, and 36 PhD students have completed their degrees under his supervision.[1]

Personal life

Cook lives with his wife in Toronto. They have two sons, one of whom is Olympic sailor Gordon Cook.[21]

See also

References

  1. 12Stephen Cook at the Mathematics Genealogy Project
  2. ↑Kapron, Bruce. "Stephen Arthur Cook". A. M. Turing Award. Retrieved October 23, 2018.
  3. ↑Richard Karp (2003). "A Personal View of Computer Science at Berkeley". University of California Berkeley. Retrieved February 12, 2023.
  4. ↑Stephen Cook (1971), The Complexity of Theorem Proving Procedures(PDF)– via University of Toronto
    Stephen A. Cook (2009) [1971]. "The Complexity of Theorem-Proving Procedures". Retrieved February 12, 2023.
  5. ↑P vs. NPArchived October 14, 2013, at the Wayback Machine problem on Millennium Prize Problems page – Clay Mathematics Institute
  6. ↑P vs. NPArchived September 27, 2007, at the Wayback Machine problem's official description by Stephen Cook on Millennium Prize Problems
  7. ↑Cook, Stephen A. (May 5, 1975). "Feasibly constructive proofs and the propositional calculus (Preliminary Version)". Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75. New York: Association for Computing Machinery. pp. 83–97. doi:10.1145/800116.803756. ISBN 978-1-4503-7419-4. S2CID 13309619.
  8. ↑Cook, Stephen A.; Reckhow, Robert A. (1979). "The Relative Efficiency of Propositional Proof Systems". The Journal of Symbolic Logic. 44 (1): 36–50. doi:10.2307/2273702. ISSN 0022-4812. JSTOR 2273702. S2CID 2187041.
  9. ↑"Logical Foundations of Proof Complexity"'s official page
  10. ↑""Steve's class": origin of SC". Theoretical Computer Science – Stack Exchange.
  11. ↑ "¿Quién introdujo la clase de complejidad AC?" . Informática teórica – Stack Exchange .
  12. ↑ "Veinte preguntas para Donald Knuth" .
  13. ↑ "Galardonado con las Medallas Honoríficas Bernard Bolzano al Mérito en Ciencias Matemáticas" . Medallas de la CAS . Academia Checa de Ciencias . Consultado el 13 de abril de 2024 .
  14. ↑ Asociación para la Maquinaria Informática. "Stephen A. Cook" . awards.acm.org . Consultado el 12 de febrero de 2023 .
  15. ↑ "Gödel Lecturers – Asociación de Lógica Simbólica" . Consultado el 8 de noviembre de 2021 .
  16. ↑ "25 personas designadas para el máximo honor de Ontario" . Ministerio de Ciudadanía e Inmigración .
  17. ↑ Emily, Chung (27 de febrero de 2013). "Científica informática gana el máximo premio científico de Canadá" . cbc.ca. Consultado el 27 de febrero de 2013 .
  18. ↑ "Ganador actual – 2012 – Stephen Cook" . 28 de junio de 2016.
  19. ↑ "SaltWire | Halifax" . www.saltwire.com . Consultado el 12 de febrero de 2023 .
  20. ↑ "Orden de Canadá: los máximos honores recaen en Janet Rossant, pionera en células madre de la Universidad de Toronto, y Bob Rae, líder en políticas públicas" . Universidad de Toronto . 2 de julio de 2015. Consultado el 2 de marzo de 2025 .
  21. ↑ "Stephen A. Cook – Página principal" .
  • 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