Richard M. Karp

Richard Karp 2009

Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie. 1985 erhielt er für seine Forschungsarbeit auf dem Gebiet der Theorie der Algorithmen den Turing Award, 2008 erhielt er den Kyoto-Preis.

Biographie

Nach der Boston Latin School besuchte er die Harvard University, wo er 1955 seinen Bachelor in Literatur, 1956 seinen Master in Mathematik und 1959 seinen Ph.D. in Angewandter Mathematik erwarb. Anschließend arbeitete er bis 1968 im IBM Thomas J. Watson Research Center. Daneben war er 1962 auf Teilzeitbasis wissenschaftlicher Assistent an der New York University, 1964 bis 1965 außerordentlicher Gastprofessor für Elektrotechnik an der University of Michigan, 1965 bis 1968 außerordentlicher Gastprofessor und ordentlicher Gastprofessor für Elektrotechnik am Polytechnic Institute of Brooklyn (in Teilzeit) und 1967 bis 1968 außerordentlicher Professor für Industrial Engineering und Management Engineering an der Columbia University (in Teilzeit). 1968 wurde er Professor für Informatik, Mathematik und Operations Research an der University of California, Berkeley. Von einer vierjährigen Periode als Professor an der University of Washington (1995 bis 1999 als Professor für Informatik und Lehrbeauftragter für molekulare Biotechnologie) abgesehen, blieb er seither in Berkeley, wo er neben der Universität auch am International Computer Science Institute und zeitweise auch am Mathematical Sciences Research Institute tätig ist bzw. war.

Karp gehört oder gehörte dem redaktionellen Beirat zahlreicher Zeitschriften an, darunter das Journal of Computer and System Sciences und die Proceedings of the National Academy of Sciences, an. Daneben war er im Fachbeirat des Max-Planck-Instituts für Informatik und beriet IBM Research, Hewlett-Packard, die Computer Professionals for Social Responsibility, das International Institute for Applied Systems Analysis und das Center for Discrete Mathematics and Theoretical Computer Science. Er war im Aufsichtsrat des Weizmann-Instituts für Wissenschaften und des Institute for Mathematics and its Applications sowie im Vorstand des Miller Institute for Basic Research in Science, und leitete u.a. die Computer Science Planning Group des National Research Council und die Sektion Computer and Information Sciences der National Academy of Sciences.

1971 entwickelte Karp mit Jack Edmonds den Edmonds-Karp-Algorithmus zur Lösung des Max-Flow-Problems in Netzwerken. 1972 veröffentlichte er einen Artikel, in dem er die NP-Vollständigkeit einer Reihe von graphentheoretischen Problemen nachwies, darunter das Hamiltonkreisproblem, das Cliquenproblem und das Rucksackproblem. Diese wurden bekannt als Karps 21 NP-vollständige Probleme. 1973 entwickelte er mit John E. Hopcroft den Algorithmus von Hopcroft und Karp zur Bestimmung einer größten Paarung in bipartiten Graphen. 1987 entwickelte er gemeinsam mit Michael O. Rabin den Rabin-Karp-Algorithmus zur String-Suche. Zu seinen Forschungsschwerpunkten gehören kombinatorische und parallele Algorithmen, Bioinformatik und Netzwerke.

Zu Karps rund 40 Doktoranden gehören Narendra Karmarkar (Fulkerson-Preis 1988) und Rajeev Motwani (Gödel-Preis 2001).

Auszeichnungen (Auswahl)

• 1977: Frederick-W.-Lanchester-Preis (mit Gerard Cornuejols, Marshall Fisher und George Nemhauser)
• 1979: Fulkerson-Preis
• 1980: Mitglied der National Academy of Sciences und der New York Academy of Sciences
• 1985: Turing Award und Mitglied der American Academy of Arts and Sciences
• 1986: Ehrendoktortitel der University of Pennsylvania
• 1989: Ehrendoktortitel des Technion
• 1990: John-von-Neumann-Theorie-Preis, Ehrendoktortitel der University of Massachusetts und Gründungs-Fellow des Institute of Combinatorics and its Applications
• 1991: Fellow der American Association for the Advancement of Science
• 1992: Mitglied der National Academy of Engineering und Ehrendoktortitel der Georgetown University
• 1994: Mitglied der American Philosophical Society und Fellow der ACM
• 1996: National Medal of Science
• 1997: Harvard Centennial Medal
• 1998: Harvey-Preis
• 2000: EATCS-Award
• 2001: Ehrendoktortitel der University of Central Florida
• 2002: Auslandsmitglied der Académie des sciences, Ehrendoktortitel der Carleton University und Fellow des Institute for Operations Research and the Management Sciences
• 2003: Ehrendoktortitel der ETH Zürich
• 2004: Benjamin-Franklin-Medaille für Informatik und Kognitionswissenschaft, sowie Ehrendoktortitel des Weizmann-Instituts für Wissenschaften und Mitglied der European Academy of Sciences
• 2008: Kyoto-Preis
• 2008: Dickson Prize in Science

Schriften

• Reducibility Among Combinatorial Problems. In: R. E. Miller, J. W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York 1972, S. 85–103.

Weblinks

 Commons: Richard Karp – Sammlung von Bildern, Videos und Audiodateien

• Literatur von und über Richard M. Karp im Katalog der Deutschen Nationalbibliothek und auf anderen Websites (Datensatz zu Richard M. Karp • PICA-Datensatz • Apper-Personensuche)
• Interview und Biografie (englisch)
• Website (englisch)