컴퓨터 과학자로서의 삶

젊은 시절의 리처드 카프​†​

리처드 카프(Richard Manning Karp)​‡​는 1935년 1월 3일에 미국 메사추세츠 주 보스턴에서 태어났다. 그는 ‘딕’이라는 애칭으로 불렸다.

그의 아버지는 하버드 대학교 졸업생이었고 고등학교에서 수학을 가르쳤다. 어머니는 고등학교를 졸업한 전업주부였다. 두 분 모두 교육에 대한 열정이 강했고 아들이 하버드 대학교에 진학하도록 이끌었다. 부모님에 대한 카프의 정은 남달랐던 듯싶다. 그는 아버지가 칠판에 분필로 완벽한 원을 그리는 모습이 부러웠다고 말하기도 했으며​4​, 튜링상 수상 강연 논문을 아버지에게 헌정하기도 했다.

그의 수학 지식이 아주 앞서 있지는 않았습니다. 자신이 가르치는 것에만 한정되어 있었죠. 하지만 교실에서 그가 가지는 존재감과 학생을 이끄는 모습을 나는 본받고 싶었습니다.​3​

앞의 이야기에서도 나와 있지만 그의 어머니는 그가 컴퓨팅의 세계에 발을 담그도록 만든 사람이다. 그녀는 네 자녀를 키운 후에 하버드 대학교 학부생으로 입학해서 57세에 학사 학위를 받았다.​3​

딕은 어릴 때부터 수학을 좋아했다. 고등학교 1학년 때는 유클리드 기하학에 빠져서 학교 수업도 빼먹고 집에서 기하학 문제를 풀기도 했다고 한다. 하지만 손을 쓰는 일에는 젬병이어서 전구를 갈거나 소프트웨어를 설치하는 일도 누군가의 도움을 받아야만 할 수 있는 사람이었다.

하버드 대학교 수학과에 입학할 정도였으면 재능은 충분했다고 보이지만 그에게 학부 생활은 그리 만족스럽지 않았다. 왜냐하면 대단한 인재들이 모인 곳이 하버드 대학교였기 때문이었다. 동기 중에 데이비드 멈퍼드David Mumford와 켄 윌슨Ken Wilson 등이 있었는데 그는 이들보다 못하다는 열등감에 빠지기도 했다.​3​ 참고로 후에 데이비드 멈퍼드는 수학의 노벨상이라고 불리는 필즈상을 수상했으며 켄 윌슨은 노벨상 자체를 수상했다.

학부 마지막 해에 그는 하버드 계산 연구실Harvard Computation Lab이 제공하는 과목을 수강했다.​§​수치해석, 확률, 통계 과목에서 그는 남들보다 뛰어난 실력을 보여주었고, 특히 하틀리 로저스Hartley Rogers 교수가 그를 크게 격려했다. 이에 힘입어 그는 대학원 입학을 결심했고 계산 연구실을 선택했다. 하틀리 로저스 교수는 환원성reducibility 연구로 유명하며 후에 리처드 카프의 NP-완전 연구에 영향을 주었다.

컴퓨터 프로그램의 분석에 그래프 이론을 적용하는 논문으로 박사 학위를 받은 그는 IBM에 취직했다. 대학 교수가 될 생각이 있었지만 당시에는 컴퓨터 과학이 별도의 학과로 만들어지기 전이어서 컴퓨팅 전공자가 대학교수 자리를 얻기는 쉽지 않았다고 한다.​2​ 그래서 여러 회사에서 면접을 봤는데 그중에 벨 연구소와 IBM 연구소도 있었다. 당시에는 벨 연구소의 위상이 IBM 연구소보다 훨씬 높았지만 급여가 상대적으로 적었다. 그리고 IBM에는 수학 전문 연구 그룹이 있었다. 그래서 딕은 IBM을 선택했다.​4​ 그를 채용했던 IBM의 담당자는 같은 연구실 선배였던 프레더릭 브룩스Frederick Brooks였다.​4​​¶​

IBM에서의 생활은 만족스러웠다. 물론 회사가 원하는 일을 해야 하기는 했으나 그가 속한 그룹에는 많은 자유가 부여되었고 뛰어난 실력자들이 많았다. 1959년부터 1968년까지 9년의 기간 동안 그는 디지털 회로 최적화, 외판원 문제 등을 다루면서 조합 최적화combinatorial optimization 연구에 빠졌고, 국립 표준 연구소의 잭 에드먼즈Jack Edmonds와는 다항 시간 계산을 함께 다루었다. 그리고 IBM 연구소에 단기 방문한 마이클 래빈​5​과는, 우연히 같은 아파트 건물에 살게 된 인연으로 인해 출근을 함께 하면서 계산 이론에 관한 정보를 많이 얻기도 했다.

1968년에 리처드 카프는 캘리포니아 대학교 버클리의 교수로 채용되었다. 그는 철저하게 강의를 준비하는 것으로 유명했고 그의 강의는 여러 번 최고의 강의로 선정되었다. IBM에서 했던 조합 계산 연구를 계속하던 그는 1971년에 스티븐 쿡의 <정리 증명 절차의 복잡성>​6​ 논문을 접한 후, 자신이 해오던 조합 계산 연구와 접점이 있음을 깨닫게 된다. 그래서 그는 쿡의 연구를 좀 더 확장하면서 다듬어 1972년에 <조합 문제에 있는 환원성>​7​ 논문을 발표했다. 이는 ‘NP-완전’을 처음으로 정의한 논문이다. 그는 21개의 문제가 NP-완전에 해당함을 증명했는데 이는 큰 반향을 일으켰다. 이 논문 이후로 NP-완전에 관한 많은 논문들이 쏟아져 나왔다.

엄청난 영향력을 가진 논문을 발표한 그는, 갑작스럽게 잠시 연구에서 손을 뗄 수밖에 없는 상황을 맞이했다. 당시 버클리에는 두 개의 컴퓨터 과학 그룹이 있었다. 하나는 전기 공학과에서 분리되어 나온 지 얼마 안 된 컴퓨터 과학과였고 다른 하나는 여전히 전기 공학과 내에 존재하는 컴퓨터 과학 연구 그룹이었다. 신생 컴퓨터 과학과는 차별화를 위해 노력했으나 그리 성공적이지 못했고 그래서 대학 본부에서는 두 그룹을 하나로 합치기로 결정했다. 결국 컴퓨터 과학과는 다시 전기 공학과에 흡수되면서 독립적인 조직 형태를 가지게 되었는데, 합쳐진 두 그룹의 불화가 상당했다. 그래서 이를 해결할 적임자가 필요했고, ‘적이 제일 없다고 알려진’ 리처드 카프가 선택되었다. 1973년부터 1975년까지 그는 연구에서 완전히 손을 떼고 행정에 전념했다.

1975년에 보직에서 물러난 그는 NP-완전 문제로 돌아왔다. NP-완전 문제는 다항 시간 내에 답을 구하기 어려운 문제들이다. 카프는 완벽한 정답을 구하지 못하는 알고리듬이더라도 실제 현장에서는 의미 있는 답을 내놓을 수 있다고 생각했다. 그래서 그는 평균적 복잡도average-case complexity 라는 개념을 파고들었다.

보직에서 물러나서 생각할 시간이 좀 생기자, 나는 이런 질문을 스스로에게 던지기 시작했습니다. “… NP-완전 문제라고 해서 모든 것이 끝났다고 생각할 필요는 없음을 보여주려면 어떻게 해야 할까?” 그리고 이런 생각이 들었습니다. “이런 문제들 중 어떤 것은, 평균적으로는 효과적으로 답을 얻을 수 있음을 보여주면 되지 않을까?”​3​

완벽하지는 않지만 평균적으로는 쓸만한 알고리듬을 찾는 과정에서 그는 과거 IBM 시절에 그의 멘토였던 마이클 래빈 교수와 다시 조우하게 된다. 두 사람은 텍스트에서 문자열을 효율적으로 찾는 알고리듬을 개발했다. 이는 래빈-카프 알고리듬이라고 불린다.

1994년에 리처드 카프는 버클리의 교수직에서 물러났다. 그가 원하지 않은 이른 은퇴였다. 대학에서 재정 문제로 결정한 사안이었다. 하지만 그는 1995년에 워싱턴 대학교의 교수로 채용되었다. 이번에는 생명공학 분야였다. 인간 게놈 프로젝트가 급부상하면서 컴퓨팅 기술을 접목하려는 시도가 벌어졌다. 그는 조합 최적화 이론이 생명공학에 기여할 수 있으리라고 생각했다. 1999년에 그는 버클리로 돌아와서 교수로 재직 중이다.

1 2 3 4