WikiDer > Richard Karp
Richard M. Karp | ||
 | ||
Richard Karp im Jahr 2009 | ||
| Persönliche Informationen | ||
| Vollständiger Name | Richard Manning Karp | |
| Geburtsdatum | 3. Januar1935 | |
| Geburtsort | Boston (Vereinigte Staaten) | |
| Wissenschaftliche Arbeit | ||
| Disziplin | Informatik | |
| Offizielle Website | ||
Richard M. Karp (Boston, 3. Januar1935) ist ein amerikanisch Informatiker an der Universität Berkeley. Für seine Beiträge zur Komplexitätstheorie er bekam die . im Jahr 1985 Turing-Preis.
Biografie
Karp wurde am 3. Januar 1935 in Boston geboren und ging in die Bostoner Lateinschule. Er studierte an der Harvard Universität und promovierte dort 1959 in angewandter Mathematik. Von 1959 bis 1968 arbeitete er in der Forschungsabteilung der IBM.
Seine wichtigsten wissenschaftlichen Beiträge leistete Karp von 1968 bis 1994 als Professor an der University of California in Berkeley. Von 1994 bis 1999 war er Professor an der Universität von Washington, danach kehrte er als Universitätsprofessor nach Berkeley zurück.
Arbeit
Karp hat wichtige Beiträge zur Komplexitätstheorie geleistet und operatives recherchieren. Heute konzentriert er sich hauptsächlich auf Bioinformatik.
1972 veröffentlichte er den Artikel Reduzierbarkeit zwischen kombinatorischen Problemen,[1] in dem er 21 ist Entscheidungsprobleme bewiesen, dass sie NP-vollständig sein, durch die Erfüllungsproblem, direkt und indirekt an sie. Damit gab er dem Studium der Komplexitätsklasse NP und ob die Komplexitätsklassen p und NP sind gleich.
Karp war Mitentdecker der Edmonds-Karp-Algorithmus um den maximalen Strom in Graphen zu bestimmen (1971), die Hopcroft-Karp-Algorithmus zur größten unabhängigen Spitzenkollektion von zweiteilige Graphen zu bestimmen (1980) und es Rabin-Karp-Algorithmus für Suche in Saiten (1987).
1980 bewies Karp zusammen mit Richard Lipton das Satz von Karp-Lipton, was besagt, dass das Erfüllbarkeitsproblem, wenn es wahr ist, gelöst werden kann durch Boolesche Schaltungen von Polynom Größe, dann die Polynomhierarchie fällt mit der zweiten Ebene zusammen.
1985 wurde Karp für seine Arbeit in der Komplexitätstheorie mit dem a Turing-Preis und 1996 a Nationale Medaille der Wissenschaft.
Siehe auch
Quellen, Anmerkungen und/oder Verweise
|