 |
Richard Manning KarpAmerican computer scientist
Date of Birth: 03.01.1935
Country:  USA |
Content:
- Richard Karp: A Computational Titan
- Early Life and Education
- Academic and Research Career
- Notable Contributions
- NP-Completeness (1972)
- Rabin-Karp String Search Algorithm (1987)
- Recognition and Impact
Richard Karp: A Computational Titan
Richard Karp, a prominent American computer scientist renowned for his contributions to the theory of computing, was born in 1935 in Boston, Massachusetts.
Early Life and Education
Karp's father, Abraham Louis Karp, was a mathematics teacher and high school principal, while his mother, Rose Karp, fostered an environment that nurtured his intellectual curiosity. Karp graduated from high school and enrolled at Harvard University, where he earned a Bachelor of Arts in 1955, a Master of Science in 1956, and a Doctor of Philosophy in Applied Mathematics in 1959.
Academic and Research Career
After completing his PhD, Karp embarked on a nine-year tenure at IBM's Thomas J. Watson Research Center. In 1968, he joined the University of California, Berkeley, as a Professor of Computer Science, Mathematics, and Operations Research, a position he still holds today, excluding a four-year stint at the University of Washington.
Notable Contributions
Max Flow Algorithm (1971)In collaboration with Jack Edmonds, Karp developed an algorithm for finding the maximum flow in a transportation network, which bears their names.
NP-Completeness (1972)
Karp's seminal paper, "Reducibility Among Combinatorial Problems," demonstrated the NP-completeness of 21 problems, laying the foundation for understanding the complexity of computation.
Rabin-Karp String Search Algorithm (1987)
Together with Michael Rabin, Karp devised an algorithm for searching for substrings, which is named after them.
Recognition and Impact
Karp's work has been widely cited, earning him the honor of being ranked 35th on CiteSeer's list of most-cited authors in 2009. His contributions have had a profound impact on the field of computer science, shaping our understanding of complexity theory and algorithms.
