Richard M. Karp

(미국 컴퓨터과학자, 1935~)

Richard M. Karp 는 알고리즘이론의 연구로 유명한 컴퓨터과학자로서 1985 년에 Turing Award 를 수상했다. 그는 보스톤에서 출생하여 하바드 대학에서 응용수학 (applied mathematics) 로 1959 년에 박사학위를 받았다. IBM Thomas J. Watson Research Center 에서 잠시 있었고, University of California, Berkeley 에서 컴퓨터과학, 수학, 경영과학 (operations research) 교수를 지냈으며 잠시 University of Washington 에 있었다. 그는 계산복잡도 (computational complexity) 의 업적으로 2004 Benjamin Franklin Medal in Computer and Cognitive Science 를 수상했다. 튜링상을 수상하면서 그의 업적을 다음과 같이 묘사했다.

• 그는 알고리즘이론 (theory of algorithms) 에 많은 공헌을 하였는데, 특히 network flow 와 많은 combinatorial optimization problems 를 위한 효율적인 알고리즘의 개발, 알고리즘 효율성을 직관적으로 표현한 polynomial-time computability 의 인식, 가장 유명한 것은 NP-completeness 이론에 공헌하였다는 것이다. 즉 컴퓨터가 계산하기 어려운 (computationally difficult) 많은 이론적 실제적 문제들을 인식하게한 NP-complete 문제들을 증명하는 표준적인 방법들을 소개했다.

1971 년에 Jack Edmonds 와 함께 네트워크에서 max-flow problem 을 해결하는 Edmonds-Karp algorithm 를 개발했다. 1987 년에는 Michael O. Rabin 과 함께 Rabin-Karp string search algorithm 을 개발했다. 그는 컴퓨터과학과 경영과학에서의 combinatorial algorithms 영역에서 많은 중요한 발견을 했다. 최근에는 bioinformatics 분야를 연구하고 있다. .......... (Wikipedia : Richard Karp)

term :

알고리즘 (Algorithm)   조합최적화 (Combinatorial Optimization)   계산 (Computation)   계산복잡도 이론 (Computational Complexity Theory)   비결정 완전 (NP-complete)   경영과학 (Operation Research)   Michael Rabin   Richard Karp   A.M. Turing Award

site :

ACM Crossroads magazine interview/bio of Richard Karp

Karp's Home Page at Berkeley 

Karp at ICIR : papers

paper :

Reducibility among combinatorial problems. In Miller, R. E. & Thatcher, J. W., editors, Complexity of Computer Computations, Plenum, New York. 1972

video :

Heuristics for NP-Hard Problems : Richard Karp : 2011/10/16