스티븐 쿡

3. 연구 업적

쿡은 박사 학위 과정 동안 함수의 복잡성, 주로 곱셈에 대해 연구했다. 1982년, 쿡은 복잡성 이론에 기여한 공로로 튜링상을 받았다. 수상 이유는 다음과 같다.

> 계산 복잡성에 대한 우리의 이해를 중요하고 심오한 방식으로 발전시킨 공로. 그의 기념비적인 논문인 "정리 증명 절차의 복잡성"은 1971년 ACM SIGACT 컴퓨팅 이론 심포지엄에서 발표되었으며, NP-완전성 이론의 기초를 놓았다. NP-완전 문제의 경계와 본질에 대한 후속 탐구는 지난 10년 동안 컴퓨터 과학에서 가장 활발하고 중요한 연구 활동 중 하나였다.

쿡의 주요 연구 분야는 계산 복잡성 이론과 증명 복잡성이며, 프로그래밍 언어 의미론, 병렬 계산, 인공 지능 분야에도 관심을 가졌다. 그가 기여한 다른 분야로는 제한된 산술, 제한된 역수학, 고차 함수 복잡성, 분석의 복잡성, 명제 증명 시스템의 하한이 있다. 닉 피펜저의 이름을 따서 복잡도 종류 NC를 명명했다. 복잡도 종류 SC는 그의 이름을 따서 명명되었다.^[9] 복잡도 종류 AC⁰의 정의와 그 계층 AC 또한 그에 의해 도입되었다.^[10]

3. 1. P 대 NP 문제와 NP-완전성

3. 2. 증명 복잡성

3. 3. 기타 연구 분야

4. 수상 및 영예

스티븐 쿡은 1977년 NSERC E.W.R. 스테이시 기념 펠로우십, 1982년 킬럼 연구 펠로우십을 받았으며, 1999년에는 CRM-Fields-PIMS 상을 수상했다. 존 L. 싱게 상과 체코 과학 아카데미의 베르나르트 볼차노 메달(2008년)을 수상했으며,^[12] 런던 왕립 학회와 캐나다 왕립 학회의 펠로우이다. 미국 국립 과학 아카데미 (미국) 및 미국 예술 과학 아카데미 회원으로 선출되었다. 괴팅겐 과학 인문 아카데미의 통신 회원이다.

1982년에 ACM 튜링상을 수상했다. 컴퓨팅 기계 협회는 2008년 그의 ''계산 복잡성 이론에 대한 근본적인 기여''를 인정하여 ACM 펠로우로 선정했다.^[13]

온타리오 주 정부는 2013년 온타리오 훈장에 임명했는데, 이는 온타리오에서 가장 높은 영예이다.^[15] 2012년 제라드 허츠버그 캐나다 과학 및 공학 골드 메달을 수상했으며, 이는 캐나다의 과학자 및 엔지니어에게 주어지는 최고 영예이다.^[16] 2015년에 캐나다 훈장 오피서로 임명되었다.^[18]

"컴퓨터가 효율적으로 해결할 수 있는 것과 없는 것을 식별하는 데 중요한 역할을 한 공로"로 2015년 정보 통신 기술 부문에서 BBVA 재단 지식의 개척자 상을 수상했다.

5. 개인 생활

쿡은 토론토에 아내와 함께 거주하며, 슬하에 두 아들을 두고 있다. 그 중 한 명은 올림픽 요트 선수인 고든 쿡이다.^[20] 취미는 바이올린과 요트이다.

참조

_[1] 웹사이트 Stephen Arthur Cook https://amturing.acm[...] 2018-10-23
_[2] 웹사이트 A Personal View of Computer Science at Berkeley https://www2.eecs.be[...] 2023-02-12
_[3] 웹사이트 The Complexity of Theorem Proving Procedures 1971
_[3] 웹사이트 The Complexity of Theorem-Proving Procedures http://4mhz.de/cook.[...] 2023-02-12
_[4] 웹사이트 P vs. NP http://www.claymath.[...]
_[4] Webarchive https://web.archive.[...] 2013-10-14
_[5] 웹사이트 P vs. NP http://www.claymath.[...]
_[5] Webarchive https://web.archive.[...] 2007-09-27
_[6] 서적 Proceedings of seventh annual ACM symposium on Theory of computing - STOC '75 Association for Computing Machinery 1975-05-05
_[7] 간행물 The Relative Efficiency of Propositional Proof Systems 1979
_[8] 웹사이트 Logical Foundations of Proof Complexity http://www.cup.es/us[...]
_[9] 웹사이트 "Steve's class": origin of SC https://cstheory.sta[...]
_[10] 웹사이트 Who introduced the complexity class AC? https://cstheory.sta[...]
_[11] 웹사이트 Twenty Questions for Donald Knuth http://www.informit.[...]
_[12] 웹사이트 Awarded The Bernard Bolzano Honorary Medals for Merit in the Mathematical Sciences https://www.avcr.cz/[...] Czech Academy of Sciences 2024-04-13
_[13] 웹사이트 Stephen A Cook https://awards.acm.o[...] 2023-02-12
_[14] 웹사이트 Gödel Lecturers – Association for Symbolic Logic https://aslonline.or[...] 2021-11-08
_[15] 웹사이트 25 Appointees Named to Ontario's Highest Honour http://news.ontario.[...]
_[16] 뉴스 Computer scientist wins Canada's top science prize https://www.cbc.ca/n[...] cbc.ca 2013-02-27
_[17] 웹사이트 Current Winner – 2012 – Stephen Cook http://www.nserc-crs[...] 2016-06-28
_[18] 웹사이트 SaltWire | Halifax https://www.saltwire[...] 2023-02-12
_[19] MathGenealogy
_[20] 웹사이트 Stephen A. Cook – Home Page http://www.cs.toront[...]
_[21] 문서 A Personal View of Computer Science at Berkeley - Richard Karp http://www.eecs.berk[...]
_[22] 문서 "The Complexity of Theorem Proving Procedures" http://www.cs.toront[...]
_[23] 문서 "The Complexity of Theorem Proving Procedures" http://4mhz.de/cook.[...]
_[24] 웹사이트 P vs. NP http://www.claymath.[...]
_[24] Webarchive https://web.archive.[...] 2013-10-14
_[25] 문서 P vs. NP http://www.claymath.[...]
_[26] 문서 "Feasibly Constructive Proofs and the Propositional Calculus" http://doi.acm.org/1[...]
_[27] 문서 "The Relative Efficiency of Propositional Proof Systems" http://www.jstor.org[...]
_[28] 웹사이트 "Logical Foundations of Proof Complexity" http://www.cup.es/us[...]
_[29] 웹사이트 Stephen Cook http://fellows.acm.o[...]