Richard M. Karp
Computer scientist who showed that many everyday problems are NP-complete
- Age
- 91 yrs
- Birthday in 58 days
- Works listed
- 2
- Paper, Algorithm
- Honours
- 3
- Most recent 2008
- Profile views
- 4
- 0 followers
Richard Karp is an American computer scientist who showed in 1972 that 21 common problems, such as scheduling and route-finding, are NP-complete. He co-created several important algorithms and later worked in computational biology. He received the Turing Award in 1985.
Biography
Education
Karp earned all his degrees at Harvard, finishing his PhD in applied mathematics in 1959. He then spent a decade at IBM’s Thomas J. Watson Research Center.
21 NP-complete problems
In his 1972 paper “Reducibility Among Combinatorial Problems”, Karp built on Stephen Cook’s work to show that 21 well-known problems — including the travelling salesman problem, graph colouring and the knapsack problem — are all NP-complete. The paper showed that NP-completeness is everywhere in practice.
Algorithms
He co-invented the Edmonds–Karp algorithm for network flow, the Hopcroft–Karp algorithm for matching and, with Michael Rabin, the Rabin–Karp string-search algorithm.
Berkeley and biology
Karp has taught at the University of California, Berkeley, since 1968 and was founding director of the Simons Institute for the Theory of Computing. Since the 1990s he has worked on algorithms for genome analysis.
Timeline
-
1935
Born in Boston, Massachusetts, United States
-
1959
PhD from Harvard; joins IBM Research
-
1968
Joins UC Berkeley
-
1972
Shows 21 problems are NP-complete
-
1985
Turing Award
-
1996
National Medal of Science
-
2008
Kyoto Prize
-
2012
Founding director of the Simons Institute
Notable works
-
1972
Reducibility Among Combinatorial Problems Paper
-
1972
Edmonds–Karp algorithm Algorithm
With Jack Edmonds.
Awards and honours
-
Turing Award
1985
-
National Medal of Science
1996
-
Kyoto Prize
2008
Did you know?
-
1
His list of 21 problems is often the starting point for proving a new problem is hard.
-
2
He has worked on gene and protein network analysis.
-
3
He co-created algorithms with both Michael Rabin and John Hopcroft.
Connections
Related people
Also born on 3 January
Frequently asked
Who is Richard M. Karp?
Richard Karp is an American computer scientist who showed in 1972 that 21 common problems, such as scheduling and route-finding, are NP-complete. He co-created several important algorithms and later worked in computational biology. He received the Turing Award in 1985.
How old is Richard M. Karp?
Richard M. Karp is 91 years old, born on 3 January 1935 in Boston, Massachusetts, United States.
Where is Richard M. Karp from?
Richard M. Karp was born in Boston, Massachusetts, United States.
What is Richard M. Karp known for?
Richard M. Karp is best known for Karp’s 21 NP-complete problems; Edmonds–Karp and Rabin–Karp algorithms; Turing Award 1985.
What awards has Richard M. Karp received?
Notable honours include Turing Award (1985), National Medal of Science (1996), Kyoto Prize (2008).
References
- Richard M. Karp — Wikipedia. Wikipedia. Retrieved 4 November 2026.
- Richard M. Karp — Britannica. Encyclopaedia Britannica. Retrieved 4 November 2026.
- Official website. www.eecs.berkeley.edu. Retrieved 4 November 2026.
- Richard M. Karp (Q92612) — structured data. Wikidata. Retrieved 4 November 2026.
Includes material from the Wikipedia article “Richard M. Karp”, licensed under CC BY-SA 4.0. That text is available under the same licence. Learn more
External links
About this profile
- Researched by the TrackFame editorial team; reviewed by Sanjay Sokal under our editorial policy
- First published 4 November 2026
- Last updated
Cite this page
“Richard M. Karp.” TrackFame, last updated 5 November 2026. https://trackfame.com/person/richard-karp
Discussion 0
Sign in or create an account to join the discussion.
No comments yet — be the first.
More in Science
Science
Margaret Hamilton
MIT engineer who led the software for the Apollo Moon landings and coined “software engineering”
1936 – 2026
Science
Marvin Minsky
Co-founder of MIT’s artificial intelligence laboratory and a founding father of AI
1927 – 2016
Science
Michael Faraday
Self-taught scientist who discovered electromagnetic induction
1791 – 1867
Science
Nikola Tesla
Serbian-American inventor of the alternating-current induction motor
1856 – 1943
Science
Yann LeCun
French-American AI pioneer who invented convolutional neural networks
Born 1959
Science
Peter Norvig
Google’s former director of research and co-author of the leading AI textbook
Born 1956