Stephen  Cook

 (캐나다 컴퓨터과학자, 수학자, 1939~)

버팔로에서 태어나 1962 년 하바드에서 박사학위를 받았다. 1970 년 이래로 Toronto 대학 교수로 있다. 그의 주요 연구분야는 계산복잡도이론 (Computational Complexity Theory), 프로그래밍 언어 의미론, 병렬계산, 논리와 복잡도이론 간의 접점 연구등이다.

그는 계산의 복잡도를 이해하기 위한 중요하고 심오한 방법을 제시하였다. 1971 ACM SIGACT Symposium에서 발표된 논문 "The Complexity of Theorem Proving Procedures," 에서는 Theory of Computing, NP-Completeness 이론으로 유명하다. NP-complete 문제 부류의 경계선과 성격에 대한 탐구는 최근 컴퓨터과학에서 가장 중요한 연구활동중의 하나로 알려져있다. 1982 년에 Alan Turing 상을 수상하였다.

스티븐 쿡과 레오니드 레빈 : Dennis Shasha : .... 순회판매원 문제 (Travelling Salesman Problem) 에서 ...... 만일 100 개의 도시가 있다면 100 의 계승에 해당하는 여행 방법들을 평가해야 합니다. 어떠한 컴퓨터도 100 의 계승만큼의 여행 방법을 시도해 볼 수는 없을 것입니다. 사람들이 그것을 이해하기는 어렵지요. 몇 가지 간단한 계산을 해 보면, 만일 당신이 태양계에서 각각의 회전수에 비할 만한 빈도로 그것에 작용하는 모든 전자들을 가지고 있을 경우, 그것을 찾는 데에는 태양이 다 타 버릴  때까지 시간이 걸릴 것이란 사실을 깨달을 수 있습니다. 우리가 이해해야 할 기본적인 요점은 실제로 실행에 옮길 수 없는 일들이 존재한다는 사실입니다.

서구 계산 이론의 전통에서 계산의 난이도라는 개념은 논리학과 앨런 튜링이 제시한 '계산 불가능성' 의 연구 결과에 뿌리를 두고 있다. 마이클 라빈은 1959 년 계산 가능한 문제들의 고유한 난이도라는 개념을 최초로 공식화하였다. 1971 년 비다항식 완전 문제를 정의하면서 스티븐 쿡은 이같은 전통을 따르고 있었다.

'비다항식 완전 문제가 철저한 조사를 필요로 하는가 아니면 필요로하지 않는가?' 라는 문제이다. 그것을 다른 식으로 표현하면 다음과 같다. 즉, 세일즈맨의 여행 문제와 같은 문제들에 대해 가능한 경로들 가운데 오로지 어떤 작은 부분만을 검토하면서 그 문제를 해결할 수 있는 알고리즘이 컴퓨터 과학의 역사를 변화시킬 것이란 이야기이다. ..........

NP=P 를 증명할 수 있지 않을까? 다시 말해, 다항식 시간 내에 그 해법이 '해결' 될 수 있는 문제가 다항식 시간 내에 '검토' 될 수도 있을까? (그림 2 참조)

이와 같은 사례에서 어떤 진전이 있는지를 말하기는 어렵습니다. 그것은 곧 임박한 것이 아니라, 단지 부분적인 결과들이 있을 뿐입니다. 사람들은 각기 다른 수많은 영역에서 그 문제를 공략하고 있습니다. 그리고 어찌되었든 P = NP 가 되는 것은 가능합니다.

term :

Stephen Cook    계산복잡도이론 (Computational Complexity Theory)    NP-complete     순회판매원 문제 (Traveling Salesman Problem)     튜링 상(Turing Award)    Leonid Levin

site :

Wikipedia : Stephen Cook

Stephen Cook's home page : Toronto 대학 컴퓨터과학과, Biography

video :

The Ultimate Limits of Computers : Techfest 2013 Bombay : Stephen Cook, 2013/05/06

Interview with Prof. Stephen A. Cook, 2012 Winner of NSERC's Herzberg Medal : Stephen Cook, 2013/02/27

NSERC Presents 2 Minutes with Stephen Cook : NSERCTube : Stephen Cook, 2013/02/27