Richard M. Karp

Die Veröffentlichung des Artikels „Reducibility Among Combinatorial Problems“ im Jahr 1972 etablierte Richard M. Karp als eine grundlegende Figur in der Theorie der Berechnungskomplexität. Indem er bewies, dass 21 verschiedene Probleme NP-vollständig sind, lieferte er die notwendige Methodik für Forscher, um zu identifizieren, welche theoretischen und praktischen Herausforderungen in der Informatik mit effizienten Algorithmen in polynomieller Zeit grundsätzlich schwer zu lösen sind.

Akademische Grundlagen und frühe Karriere

Richard Manning Karp wurde 1935 in Boston geboren und absolvierte seine gesamte akademische Ausbildung an der Harvard University. Er erwarb 1955 einen Bachelor-Abschluss, 1956 einen Master-Abschluss und promovierte 1959 in angewandter Mathematik an der Harvard School of Engineering and Applied Sciences. Nach seinem Studium begann er seine berufliche Laufbahn am IBM Thomas J. Watson Research Center.

Entwicklung kombinatorischer Algorithmen

Karps Arbeit umfasst mehrere Jahrzehnte algorithmischer Entwicklung. 1962 arbeitete er mit Michael Held zusammen, um den Held-Karp-Algorithmus für das Problem des Handlungsreisenden zu entwickeln. Darauf folgte 1971 der Edmonds-Karp-Algorithmus, der gemeinsam mit Jack Edmonds zur Lösung von Problemen des maximalen Flusses in Netzwerken entwickelt wurde. 1973 entwickelte er zusammen mit John Hopcroft den Hopcroft-Karp-Algorithmus, der bis heute die schnellste Methode zur Identifizierung maximaler Kardinalitäts-Matchings in bipartiten Graphen ist. Darüber hinaus arbeitete er 1987 mit Michael O. Rabin zusammen, um den Rabin-Karp-Algorithmus zur Zeichenkettensuche mitzuentwickeln.

Institutionelle Rollen und Anerkennung

1968 trat Karp in die Fakultät der University of California, Berkeley, ein, wo er als erster stellvertretender Vorsitzender der Computer Science Division fungierte. Abgesehen von einer vierjährigen Professur an der University of Washington hat er seine Verbindung zu Berkeley beibehalten. 2012 wurde er Gründungsdirektor des Simons Institute for the Theory of Computing. Seine wissenschaftlichen Beiträge wurden mit zahlreichen Auszeichnungen gewürdigt, darunter der Turing Award 1985, der Harvey-Preis 1998, die Benjamin Franklin Medal 2004, der Kyoto-Preis 2008 und der Dickson-Preis 2009.

Fakten

- Geboren: 1935, Boston, Massachusetts - Ausbildung: Harvard University (B.S., M.S., Ph.D.) - Hauptzugehörigkeit: University of California, Berkeley - Turing Award: 1985 - Kyoto-Preis für Hochtechnologie: 2008 - Hauptforschungsgebiete: Bioinformatik und theoretische Informatik - Wichtige Publikation von 1972: Reducibility Among Combinatorial Problems - Gründungsdirektor: Simons Institute for the Theory of Computing

Häufig gestellte Fragen

### Was ist die Bedeutung des Artikels von Richard Karp aus dem Jahr 1972?

Er bewies, dass 21 verschiedene Probleme NP-vollständig sind, und lieferte damit eine Standardmethodik zur Klassifizierung der rechnerischen Schwierigkeit von Problemen.

### Welche bedeutenden Auszeichnungen hat Richard Karp erhalten?

Er hat unter anderem den Turing Award, den Kyoto-Preis, den Harvey-Preis, die Benjamin Franklin Medal und den John von Neumann Theory Prize erhalten.