리처드 M. 카프(Richard Manning Karp, 1935년 1월 3일 ~ )는 미국의 저명한 전산학자이며 수학자이다. 그는 알고리즘 이론과 계산 복잡도 이론, 특히 NP-완전성 이론에 대한 선구적인 공헌으로 가장 잘 알려져 있다. 1985년에는 "알고리즘 이론, 특히 NP-완전성 이론에 대한 지속적인 기여"를 인정받아 튜링상을 수상했다. 현재 캘리포니아 대학교 버클리 캠퍼스에서 명예 교수로 재직 중이다.
생애 및 학력
카프는 1935년 1월 3일 미국 매사추세츠주 보스턴에서 태어났다. 그는 하버드 대학교에서 응용수학을 전공하여 학사, 석사, 박사 학위를 취득했다. 박사 학위는 1959년에 받았다. 이후 IBM 토마스 J. 왓슨 연구소 등에서 근무했으며, 1968년부터 캘리포니아 대학교 버클리 캠퍼스 교수로 재직했다.
주요 연구 및 기여
리처드 카프의 가장 중요한 공헌은 계산 복잡도 이론, 특히 NP-완전성 이론에 있다. 그는 스티븐 쿡의 NP-완전성 개념을 확장하여, 1972년 논문 "Reducibility Among Combinatorial Problems"를 통해 21가지의 광범위한 조합론적 및 그래프 이론 문제를 NP-완전 문제로 증명했다. 이 논문에서 그는 한 문제가 다른 문제로 다항 시간 내에 변환될 수 있음을 보여주는 "카프 환원(Karp reduction)"이라는 개념을 도입하여, 수많은 중요한 문제들이 본질적으로 같은 난이도를 가진다는 것을 입증했다. 이 연구는 계산 복잡도 이론의 발전과 NP-완전성 연구의 폭발적인 성장에 결정적인 영향을 미쳤다.
그 외에도 그는 네트워크 흐름, 조합 최적화, 병렬 알고리즘 등 다양한 분야에서 중요한 연구를 수행했다.
수상
- 1985년: 튜링상 (ACM)
- 1996년: 미국 국가 과학 메달
- 2004년: 교토상 (첨단 기술 부문)
- 2008년: 에러디쉬상 (Erdős Prize)
같이 보기
- NP-완전 문제
- 튜링상
- 스티븐 쿡
- 계산 복잡도 이론