컴퓨터 과학자로서의 삶

젊은 시절의 스티븐 쿡(1968년)​‡​

스티븐 쿡(Stephen Arthur Cook)은 1939년 12월 14일에 미국 뉴욕주 버펄로에서 태어났다. 그의 아버지는 유니온 카바이드의 자회사에서 화학자로 일했으며 뉴욕 주립대 버펄로SUNY Buffalo에서 겸임교수를 지내기도 했다.

그는 10대 시절에 전자공학에 관심이 많았는데 고등학생 때는 같은 동네에 살던 윌슨 그레이트배치Wilson Greatbatch의 작업장에서 조수로 일하기도 했다. 윌슨 그레이트배치가 만들던 회로는 후에 최초의 인공심박조율기 발명으로 이어졌고 그레이트배치는 미국 발명가의 전당에 헌액되었다.

그가 그 일을 하고 있을 때 나는 고등학생이었습니다. 나는 그를 도왔는데 그의 차고 위에 차려진 작은 작업장에서 일했습니다. 그가 트랜지스터를 사용한 회로를 설계하면 내가 납땜질을 했습니다. 그렇게 만들어진 것을 그가 시험할 때, 나는 오실로스코프에 “빕, 빕, 빕”하면서 뭐가 나타나는 것을 볼 수 있었습니다.​2​

자연스럽게 그는 대학에 진학할 때도 공대를 선택했다. 부모님이 모두 미시간 대학교 졸업생이었고 친형도 미시간 대학교에 입학했기 때문에 그도 자연스럽게 미시간 대학교에 입학했다. 그런데 미적분학 수업에서 두각을 나타내면서 교수의 눈에 들게 된다. 담당 교수는 1학년 2학기에 3학년 수업을 수강하라고 추천해 주었고 결국 그는 3학년 때에 수학과로 옮겼다.

하버드 대학교 수학과에 석사로 입학한 그는 1년 만에 학위를 받고 박사 학위 과정에 진학했다. 그의 연구 주제는 계산 복잡도Computational complexity 였는데 세 명으로부터 큰 영향을 받았다. 먼저 계산 복잡도라는 용어를 만든 장본인 중 한 명인 유리스 하트마니스Juris Hartmanis가 있다.​§​ 1963년에 그는 하버드 대학교를 방문해서 계산 복잡도에 관한 강연을 했고, 이 강연을 계기로 스티븐은 계산 복잡도에 관심을 가지게 되었다.​2​

두 번째 인물은 앨런 코밤Alan Cobham이다. 그는 하버드 대학교 수학과 박사 과정 학생으로 스티븐보다 몇 년 선배였다. 코밤은 박사 논문을 다 작성했지만 학위 심사 요건에 필요한 추가 논문 작성을 귀찮아했고 결국 학위를 받지 않고 그냥 IBM 왓슨 연구소로 취직해 버렸다.​2​ 아무튼 그의 박사 논문은 계산 복잡도에 관한 것이었고, ‘곱셈이 덧셈보다 왜 더 어려운가?’에 관한 연구였다. 참고로 스티븐의 박사 논문 주제도 곱셈의 계산 복잡도였다. 그런데 스티븐에게 더 큰 영향을 준 내용이 있다. 코밤은 다항 시간 계산 함수polynomial-time computable functions라는 개념을 소개했다. P와 NP 문제를 설명할 때 사용되는 다항 시간 계산polynomial-time computation이 여기서 등장한 셈이다. (참고로 NP-완전으로 튜링상을 수상한 또 다른 컴퓨터 과학자인 리처드 카프의 경우, 다른 과학자로부터 다항 시간 계산에 관한 아이디어를 얻었다. 비슷한 시기에 같은 아이디어가 동시다발적으로 나타난 예이다.)

마지막 인물은 그의 논문 지도 교수였던 하오 왕Hao Wang이다. 그는 응용 물리학과 교수였지만 논리학자였고 특히나 그의 관심은 힐베르트의 결정문제Entscheidungsproblem이었다. 그는 어떤 술어 계산predicate calculus 공식이 주어졌을 때 이것이 충족가능한지satisfiable 아닌지를 결정할 방법이 있는지에 관심을 가졌다. 이 문제는 후에 스티븐이 NP-완전complete 개념을 제시할 때 핵심적인 내용이 된다.

1966년에 곱셈의 계산 복잡도에 관한 논문으로 박사학위를 받은 스티븐은 캘리포니아 대학교 버클리에서 계약직 조교수로 채용되었다. 그는 수학과에 속했지만 컴퓨터 센터에서도 일했다.

그가 NP 문제를 처음 머릿속에 떠올린 것은 1967년이었다고 한다.

처음에 나는 원시재귀함수primitive recursive functions의 모임class에 관한 글들을 등사기로 복사해서 사람들과 돌려보았습니다… 당시에 프린스턴의 논리학자가 진행한 연구가 있었습니다…. 그는 한 번도 튜링 기계를 언급하지 않았지만 그가 거론한 복잡도 모임complexity class 중 하나는 사실상 extended positive rudimentary relation이었습니다… 결국 나는 깨달았습니다. “이게 뭐야? 이건 비결정적 다항 시간nondeterministic polynomial time이잖아.” 아마도 그때가 내가 처음으로 오늘날 ‘NP’라고 부르는 것에 관심을 가지게 된 때가 아닌가 싶습니다.​2​

1970년에 스티븐은 종신 교수직 심사에서 떨어지면서 버클리를 그만두게 되었다. 하지만 다행히 토론토 대학교에서 자리를 제안했고 그는 컴퓨터 공학과 조교수로 채용되었다. 1971년에 그는 <정리 증명 절차의 복잡성​3​>이라는 논문을 발표했고 여기서 NP-완전complete 개념을 최초로 제시했다. 그는 이 논문에서 NP-완전complete에 해당하는 문제를 3개 제시했는데 바로 다음 해에 리처드 카프Richard Karp 가 21개의 사례를 찾아냈고 그 후로 계속 추가되었다.​¶​

스티븐은 계산 복잡도 외에도 병렬 처리 회로, 프로그래밍 언어 의미 검증 등에서도 주목할 만한 연구 결과를 발표했다. 그는 아직도 토론토 대학교에서 교수로 활동하고 있으며 로열 캐나다 요트 클럽의 회원이기도 하다.

1 2 3 4