스티븐 쿡

1. 개요

스티븐 쿡은 계산 복잡성 이론과 증명 복잡성 분야에 기여한 캐나다-미국 컴퓨터 과학자이다. 1966년 하버드 대학교에서 박사 학위를 받았으며, 1970년부터 토론토 대학교에서 교수로 재직했다. 1971년 논문에서 다항 시간 환원과 NP-완전성의 개념을 공식화하고, 부울 만족 가능성 문제(SAT)가 NP-완전임을 증명하여 NP-완전 문제의 존재를 입증했다. 이 연구는 P 대 NP 문제의 제기로 이어졌으며, 1982년 튜링상 수상의 기반이 되었다. 그는 또한 증명 복잡성 분야를 개척하고, 다양한 상을 수상하며 학계에서 중요한 업적을 남겼다.

2. 경력

3. 연구 업적

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

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

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

3.1. P 대 NP 문제와 NP-완전성

쿡은 1971년 "정리 증명 절차의 복잡성"이라는 논문에서 P 대 NP 문제를 제기하고, NP-완전 개념을 최초로 정립했다. 이 논문에서 쿡은 다항 시간 환원(쿡 환원) 개념을 소개하고, 부울 만족 가능성 문제(SAT)가 NP-완전임을 증명하여 NP-완전 문제의 존재를 보였다. 이 정리는 소련의 레오니트 레빈도 독립적으로 증명하여 쿡-레빈 정리라고 불린다.

"P 대 NP" 문제는 쉽게 정답을 확인할 수 있는 최적화 문제를 효율적인 알고리즘으로도 풀 수 있는지 묻는 질문이다. 쿡은 효율적인 알고리즘으로 해결할 수 없는 최적화 문제가 존재한다고 추측했는데, 즉 P는 NP와 같지 않다고 보았다. 이 추측은 계산 복잡성 이론 분야의 많은 연구를 촉발시켰지만, 아직 풀리지 않은 문제로 남아 밀레니엄 문제 중 하나로 꼽힌다.

3.2. 증명 복잡성

1975년 논문 "실현 가능한 구성적 증명과 명제 미적분"에서 쿡은 다항 시간 개념만 사용하여 증명의 개념을 공식화하기 위해 등식 이론 PV(Polynomial-time Verifiable)를 도입했다. 1979년 그의 학생 로버트 A. 렉호와 함께 쓴 논문 "명제 증명 시스템의 상대적 효율성"에서 p-시뮬레이션과 효율적인 명제 증명 시스템 개념을 공식화했는데, 이는 현재 명제 증명 복잡성이라고 불리는 영역을 시작했다. 그들은 모든 참된 공식이 짧은 증명을 갖는 증명 시스템의 존재가 NP = coNP와 동등하다는 것을 증명했다.

3.3. 기타 연구 분야

쿡의 주요 연구 분야는 계산 복잡성 이론과 증명 복잡성이며, 프로그래밍 언어 의미론, 병렬 계산, 인공 지능 분야에도 관심을 가졌다. 그가 기여한 다른 분야로는 제한된 산술, 제한된 역수학, 고차 함수 복잡성, 분석의 복잡성, 명제 증명 시스템의 하한이 있다.

닉 피펜저의 이름을 따서 복잡도 종류 NC를 명명했다. 복잡도 종류 SC는 그의 이름을 따서 명명되었다. 복잡도 종류 AC⁰의 정의와 그 계층 AC 또한 그에 의해 도입되었다.

4. 수상 및 영예

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

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

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

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

5. 개인 생활

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