# Richard M. Karp

> American theoretical computer scientist (b.1935)

**Wikidata**: [Q92612](https://www.wikidata.org/wiki/Q92612)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Richard_M._Karp)  
**Source**: https://4ort.xyz/entity/richard-m-karp

## Summary
Richard M. Karp is an American theoretical computer scientist and mathematician, born in 1935. He is widely recognized for his fundamental contributions to the theory of computation, particularly in the area of combinatorial algorithms, for which he received the Turing Award in 1985. His work has significantly impacted the understanding of computational complexity.

## Biography
*   Born: January 3, 1935, in Boston
*   Nationality: United States
*   Education: Harvard University, Harvard School of Engineering and Applied Sciences, University of California, Berkeley
*   Known for: Fundamental contributions to the theory of computation and combinatorial algorithms.
*   Employer(s): University of California, Berkeley; University of Washington
*   Field(s): theory of computation, bioinformatics

## Contributions
Richard M. Karp has made significant contributions to theoretical computer science, particularly in the design and analysis of algorithms and computational complexity theory. A notable work is "A simple algorithm for finding frequent elements in streams and bags." His foundational research in combinatorial algorithms was recognized with the Harvey Prize in 1998, specifically for his contributions to the development of numerous combinatorial algorithms. He received the Turing Award in 1985 for his work on the theory of algorithms, including the development of efficient algorithms for network flow, matching, and other combinatorial optimization problems, and for his contributions to the theory of NP-completeness. His work has provided a framework for understanding the inherent difficulty of computational problems. He also received the Fulkerson Prize in 1979 and the Kyoto Prize in Advanced Technology in 2008, further highlighting the impact of his algorithmic research.

## FAQs
### Q: What is Richard M. Karp known for?
A: Richard M. Karp is known for his fundamental contributions to the theory of computation, especially in the area of combinatorial algorithms and computational complexity. He received the Turing Award for this work in 1985.

### Q: Where did Richard M. Karp work?
A: Richard M. Karp has been employed by the University of California, Berkeley, and the University of Washington.

### Q: What awards has Richard M. Karp received?
A: Richard M. Karp has received numerous awards, including the Turing Award (1985), John von Neumann Theory Prize (1990), National Medal of Science (1996), Harvey Prize (1998), EATCS award (2000), Benjamin Franklin Medal (2004), and the Kyoto Prize in Advanced Technology (2008).

### Q: What was Richard M. Karp's field of study?
A: Richard M. Karp's primary fields of work are the theory of computation and bioinformatics. He is also identified as a mathematician and computer scientist.

## Why They Matter
Richard M. Karp's work is foundational to modern computer science, particularly in the realm of algorithms and computational complexity. His contributions, recognized by the Turing Award, established a framework for classifying the difficulty of computational problems, notably through his work on NP-completeness. This understanding has guided decades of research in algorithm design and optimization, influencing fields from artificial intelligence to operations research. Without his insights, the development of efficient problem-solving techniques and the theoretical underpinnings of what computers can and cannot efficiently do would be significantly less advanced. His role as a university teacher and doctoral advisor at institutions like the University of California, Berkeley, also indicates his lasting impact through the mentorship of numerous computer scientists.

## Notable For
*   Recipient of the Turing Award in 1985 for his contributions to the theory of algorithms.
*   Awarded the National Medal of Science in 1996.
*   Member of prestigious organizations including the National Academy of Sciences (1980) and the National Academy of Engineering (1992).
*   Received the Kyoto Prize in Advanced Technology in 2008.
*   Authored the notable work "A simple algorithm for finding frequent elements in streams and bags."

## Body

### Personal Life and Education
Richard M. Karp was born on January 3, 1935, in Boston. He is an American citizen. He pursued his education at Harvard University, the Harvard School of Engineering and Applied Sciences, and the University of California, Berkeley. His doctoral advisor was Anthony Oettinger.

### Career and Academic Affiliations
Karp has held positions at the University of California, Berkeley, and the University of Washington. His primary occupations include mathematician, computer scientist, and university teacher. His fields of work are the theory of computation and bioinformatics. He has advised numerous doctoral students, including Noam Nisan, Rajeev Motwani, Narendra Karmarkar, Barbara Simons, Eric P. Xing, Robert M. Keller, Valerie King, Raymond Reiter, Dan Gusfield, and Michael Luby.

### Key Contributions and Publications
Richard M. Karp is renowned for his fundamental contributions to the theory of computation, particularly in the area of combinatorial algorithms. A specific notable work attributed to him is "A simple algorithm for finding frequent elements in streams and bags."

### Awards and Honors
Karp has received extensive recognition for his work:
*   **Turing Award:** 1985
*   **John von Neumann Theory Prize:** 1990
*   **National Medal of Science:** 1996
*   **Harvey Prize:** 1998, for "Achievements in the areas of theoretical computer science and operations research, in particular for his fundamental contributions to the development of numerous combinatorical algorithms."
*   **EATCS award:** 2000
*   **Benjamin Franklin Medal:** 2004
*   **Kyoto Prize in Advanced Technology:** 2008
*   **Fulkerson Prize:** 1979
*   **Harvard Centennial Medal**

### Memberships
He is a member of several distinguished academic and professional societies:
*   **National Academy of Sciences:** Member since 1980
*   **National Academy of Engineering:** Member since 1992
*   **French Academy of Sciences:** Foreign member since 2002
*   **Association for Computing Machinery (ACM):** ACM Fellow since 1994
*   **Society for Industrial and Applied Mathematics (SIAM):** Fellow since 2009
*   **American Philosophical Society**
*   **American Association for the Advancement of Science**
*   **American Academy of Arts and Sciences**

```json
{
  "@context": "https://schema.org",
  "@type": "Person",
  "name": "Richard M. Karp",
  "jobTitle": "theoretical computer scientist",
  "worksFor": [
    {"@type": "Organization", "name": "University of California, Berkeley"},
    {"@type": "Organization", "name": "University of Washington"}
  ],
  "nationality": {"@type": "Country", "name": "United States"},
  "birthDate": "1935-01-03",
  "birthPlace": "Boston",
  "alumniOf": [
    {"@type": "EducationalOrganization", "name": "Harvard University"},
    {"@type": "EducationalOrganization", "name": "Harvard School of Engineering and Applied Sciences"},
    {"@type": "EducationalOrganization", "name": "University of California, Berkeley"}
  ],
  "knowsAbout": ["theory of computation", "bioinformatics"],
  "sameAs": [
    "https://www.wikidata.org/wiki/Q36578",
    "https://en.wikipedia.org/wiki/Richard_M._Karp"
  ],
  "description": "Richard M. Karp is an American theoretical computer scientist and mathematician, born in 1935, widely recognized for his fundamental contributions to the theory of computation, particularly in the area of combinatorial algorithms."
}

## References

1. Integrated Authority File
2. [Source](https://amturing.acm.org/award_winners/karp_3256708.cfm)
3. [Source](https://awards.acm.org/award_winners/karp_3256708#140)
4. [Source](https://harveypz.net.technion.ac.il/harvey-prize-laureates/)
5. [Source](https://www.ams.org/prizes-awards/pabrowse.cgi?parent_id=17)
6. [Source](https://www.kyotoprize.org/en/laureates/)
7. [Source](https://awards.acm.org/award_winners/karp_3256708#158)
8. [Source](https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows?page=2)
9. [Source](https://inf.ethz.ch/de/departement/auszeichnungen-und-rankings/ehrendoktoren.html)
10. [Source](https://www.computer.org/volunteering/awards/babbage)
11. Mathematics Genealogy Project
12. International Standard Name Identifier
13. Virtual International Authority File
14. CiNii Research
15. [Source](https://awards.acm.org/fellows/award-recipients)
16. [Source](https://www.siam.org/prizes-recognition/fellows-program/all-siam-fellows)
17. SNAC
18. Freebase Data Dumps. 2013
19. French Academy of Sciences
20. IdRef