The publication of the 1972 paper "Reducibility Among Combinatorial Problems" established Richard M. Karp as a foundational figure in computational complexity theory. By proving 21 distinct problems to be NP-complete, he provided the methodology necessary for researchers to identify which theoretical and practical challenges in computer science are fundamentally difficult to solve using efficient, polynomial-time algorithms.
Academic Foundations and Early Career
Born in Boston in 1935, Richard Manning Karp pursued his entire formal education at Harvard University. He earned a bachelor's degree in 1955, a master's degree in 1956, and completed his Ph.D. in applied mathematics in 1959 at the Harvard School of Engineering and Applied Sciences. Following his studies, he began his professional career at the IBM Thomas J. Watson Research Center.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →Development of Combinatorial Algorithms
Karp's body of work spans several decades of algorithmic development. In 1962, he collaborated with Michael Held to create the Held–Karp algorithm for the travelling salesman problem. This was followed by the 1971 Edmonds–Karp algorithm, developed with Jack Edmonds to solve network maximum flow problems. In 1973, he partnered with John Hopcroft to produce the Hopcroft–Karp algorithm, which remains the fastest method for identifying maximum cardinality matchings in bipartite graphs. Furthermore, he worked with Michael O. Rabin in 1987 to co-develop the Rabin–Karp string search algorithm.
Institutional Roles and Recognition
In 1968, Karp joined the faculty at the University of California, Berkeley, where he served as the first associate chair of the Computer Science Division. Aside from a four-year tenure as a professor at the University of Washington, he has maintained his affiliation with Berkeley. In 2012, he became the founding director of the Simons Institute for the Theory of Computing. His contributions to science have been acknowledged with numerous honors, including the 1985 Turing Award, the 1998 Harvey Prize, the 2004 Benjamin Franklin Medal, the 2008 Kyoto Prize, and the 2009 Dickson Prize.
Fast facts
- Born: 1935, Boston, Massachusetts
- Education: Harvard University (B.S., M.S., Ph.D.)
- Primary Affiliation: University of California, Berkeley
- Turing Award: 1985
- Kyoto Prize in Advanced Technology: 2008
- Key research areas: Bioinformatics and theory of computation
- Major 1972 publication: Reducibility Among Combinatorial Problems
- Founding Director: Simons Institute for the Theory of Computing
Questions readers ask
What is the significance of the 1972 paper by Richard Karp?
It proved that 21 different problems were NP-complete, providing a standard methodology for classifying the computational difficulty of problems.
Which major awards has Richard Karp received?
He has received the Turing Award, the Kyoto Prize, the Harvey Prize, the Benjamin Franklin Medal, and the John von Neumann Theory Prize, among others.
Achievements
- Turing Award — 1985
- National Medal of Science — 1996
- Notable work: A simple algorithm for finding frequent elements in streams and bags
- Affiliated with University of California, Berkeley and University of Washington
- Educated at Harvard University, Harvard School of Engineering and Applied Sciences and University of California, Berkeley
- Worked as mathematician, computer scientist and university teacher
.jpg)
