Richard Karp
contemporaryComputational Complexity Theory / Philosophy of Computationb. 1935
Richard Karp is an American computer scientist and computational theorist whose foundational work on NP-completeness has had profound implications for the philosophy of logic and the limits of computation. His 1972 proof that 21 combinatorial problems are NP-complete reshaped understanding of computational tractability and raised deep questions about the nature of mathematical and logical knowledge.
Notable Achievements
1
Proved 21 problems NP-complete in landmark 1972 paper, establishing the field of computational complexity
2
Received the Turing Award (1985) for contributions to the theory of algorithm design and analysis
3
Developed the Edmonds-Karp algorithm for maximum flow in networks
4
Pioneered the Rabin-Karp string-searching algorithm
5
Contributed to foundational questions about the epistemological limits imposed by computational intractability