Richard M. Karp

from Wikipedia, the free encyclopedia
Richard Karp 2009

Richard Manning Karp (born January 3, 1935 in Boston ) is an American computer scientist . He is responsible for important findings in complexity theory . In 1985 he received the Turing Award for his research work on the theory of algorithms , and in 2008 he received the Kyoto Prize .


After the Boston Latin School , he attended Harvard University , where he received his bachelor's degree in literature in 1955 , his master's in mathematics in 1956 and his Ph.D. in 1959. in applied mathematics . He then worked at the IBM Thomas J. Watson Research Center until 1968 . In addition, he was a part-time research assistant at New York University in 1962, an associate visiting professor of electrical engineering at the University of Michigan from 1964 to 1965, an associate visiting professor and a full visiting professor of electrical engineering at the Polytechnic Institute of Brooklyn (part-time) from 1967 to 1968 and 1967 to 1968 Associate Professor of Industrial Engineering and Management Engineering at Columbia University (part-time). In 1968 he became Professor of Computer Science , Mathematics and Operations Research at the University of California, Berkeley . Apart from a four-year period as a professor at the University of Washington (1995 to 1999 as a professor of computer science and lecturer in molecular biotechnology), he has since remained in Berkeley, where, in addition to the university, he also worked at the International Computer Science Institute and at times also at the Mathematical Sciences Research Institute is or was active.

Karp has served on or served on the editorial boards of numerous journals, including the Journal of Computer and System Sciences and the Proceedings of the National Academy of Sciences . He was also on the Advisory Board of the Max Planck Institute for Computer Science and advised IBM Research , Hewlett-Packard , the Computer Professionals for Social Responsibility , the International Institute for Applied Systems Analysis and the Center for Discrete Mathematics and Theoretical Computer Science . He was on the supervisory board of the Weizmann Institute for Science and the Institute for Mathematics and its Applications as well as on the board of directors of the Miller Institute for Basic Research in Science . a. the Computer Science Planning Group of the National Research Council and the Computer and Information Sciences Section of the National Academy of Sciences .

In 1971, Karp and Jack Edmonds developed the Edmonds-Karp algorithm for solving the max flow problem in networks. In 1972 he published an article in which he demonstrated the NP-completeness of a number of graph-theoretic problems, including the Hamilton cycle problem , the clique problem, and the backpack problem . These became known as Karps 21 NP-Complete Problems . In 1973 he developed with John Hopcroft the Hopcroft-Karp algorithm for determining a greatest pairing in bipartite graphs . In 1987 he developed the Rabin-Karp algorithm for string searches together with Michael O. Rabin . His main research interests include combinatorial and parallel algorithms, bioinformatics and networks.

Karp’s 40 doctoral students include Narendra Karmarkar ( Fulkerson Prize 1988), Phillip Gibbons ( Paris Kanellakis Prize 2019) and Rajeev Motwani ( Gödel Prize 2001).

Awards (selection)


Web links

Commons : Richard Karp  - Collection of images, videos and audio files

Individual evidence

  1. ^ Frederick W. Lanchester Prize. (No longer available online.) ( Institute for Operations Research and the Management Sciences ), archived from the original on October 2, 2015 ; accessed on February 16, 2016 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. @1@ 2Template: Webachiv / IABot /
  2. ^ Honorary Degrees Awarded Since 1954 - Senate., accessed March 12, 2015 .