Richard M. Karp

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

Biography

According to the Boston Latin School, he attended Harvard University, where in 1955 he bachelor's degree in literature in 1956 with a Masters in Mathematics and in 1959 his Ph.D. in Applied Mathematics acquired. He then worked until 1968 at the IBM Thomas J. Watson Research Center. In addition, he was in 1962 part-time research assistant at New York University, 1964-1965 Visiting Associate Professor of Electrical Engineering at the University of Michigan, 1965-1968 Visiting Associate Professor and ordinary Visiting Professor of Electrical Engineering at the Polytechnic Institute of Brooklyn ( part-time) and 1967-1968 associate Professor of Industrial Engineering and Engineering management at Columbia University ( part-time). He became professor of computer science, mathematics and operations research at the University of California, Berkeley in 1968. From a four-year period as a professor at the University of Washington (1995 to 1999 as a professor of computer science and lecturer of Molecular Biotechnology ) apart, he has since remained in Berkeley, where in addition to the University and at the International Computer Science Institute and at times also on Mathematical he Sciences research Institute is or was employed.

Karp belongs or belonged to the editorial advisory boards of numerous journals, among them the Journal of Computer and System Sciences, and the Proceedings of the National Academy of Sciences on. He was also in 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 served on the board of the Weizmann Institute of Science and the Institute for Mathematics and its Applications and the Board of the Miller Institute for Basic Research in Science, and the conductor for the Computer Science Planning Group of the National Research Council and the section Computer and Information Sciences, the National Academy of Sciences.

In 1971, Karp with Jack Edmonds Edmonds - Karp algorithm to solve the Max -flow problem in networks. In 1972 he published an article in which he proved the NP- completeness of a set of graph-theoretical problems, including the Hamilton cycle problem, the clique problem and the knapsack problem. These were 21 NP- complete problems known as Karp. In 1973 he developed with John E. Hopcroft 's algorithm Hopcroft and Karp for determining a maximum matching in bipartite graphs. In 1987, he co-developed with Michael O. Rabin Rabin - Karp algorithm for string search. His research interests include combinatorial and parallel algorithms, bioinformatics and networks.

For Karp around 40 PhD students include Narendra Karmarkar ( Fulkerson Prize in 1988 ) and Rajeev Motwani ( Gödel Prize 2001 ).

Awards (selection)

Writings

  • Reducibility Among Combinatorial Problems ( PDF, 10.9 MB). In: RE Miller, JW Thatcher ( Eds.): Complexity of Computer Computations. Plenum Press, New York 1972, pp. 85-103.
Mathematical Sciences Research Institute Hewlett-Packard Edmonds–Karp algorithm Hopcroft–Karp algorithm Frederick W. Lanchester Prize New York Academy of Sciences Warsaw American Academy of Arts and Sciences Technion – Israel Institute of Technology John von Neumann Theory Prize American Association for the Advancement of Science National Academy of Engineering American Philosophical Society Association for Computing Machinery National Medal of Science Harvey Prize University of Central Florida Carleton University Alan Perlis Maurice Wilkes James H. Wilkinson John McCarthy (computer scientist) Charles Bachman Donald Knuth Allen Newell Herbert A. Simon Kenneth E. Iverson Stephen Cook Niklaus Wirth John Cocke Manuel Blum Amir Pnueli Kristen Nygaard Ron Rivest Adi Shamir E. Allen Emerson Joseph Sifakis Charles P. Thacker Judea Pearl Leslie Lamport Integrated Authority File
682214
de