Richard Manning Karp amerikansk matematiker och datavetare

Richard Manning Karp, (född 3 januari 1935, Boston, Mass., USA), amerikansk matematiker och datavetare och vinnare av 1985 AM Turing Award, den högsta ära inom datavetenskap, för "hans fortsatta bidrag till teorin om algoritmer inklusive utveckling av effektiva algoritmer för nätverksflöde och andra kombinatoriska optimeringsproblem, identifiering av polynomitidberäknbarhet med den intuitiva uppfattningen om algoritmisk effektivitet, och framför allt bidrag till teorin om NP-fullständighet. " Hans forskningsintressen har inkluderat teoretisk datavetenskap, kombinatoriska algoritmer, diskret sannolikhet, beräkningsbiologi och internetalgoritmer.

Karp fick en kandidatexamen (1955), en magisterexamen (1956) och en doktorsexamen (1959), allt i matematik, från Harvard University. Efter att ha avslutat sina studier arbetade han som matematiker på IBM (1959–68) innan han flyttade till akademin. Karp hade positioner vid University of California, Berkeley (1968–94), University of Washington (1995–99), och igen vid Berkeley (1999–), där han återvände som universitetsprofessor.

Karps artikel "Reducibility Among Combinatorial Problems" från 1972 bevisade att många vanligt studerade kombinatoriska problem är varianter av samma problem, vilket innebär att de förmodligen är oöverträffade (NP-kompletta problem - det vill säga problem för vilka ingen effektiv lösningsalgoritm är känd). Karp är författaren till Complexity of Computation (1974) och innehar ett patent för en typ av nätverk med flera kopplingar.

Förutom Turing Award fick Karp Fulkersonpriset i diskret matematik (1979), USA: s nationella medalj för vetenskap (1996), Harvard University Centennial Medal (1997), Israel Institute of Technology Harvey Prize (1998), Carnegie Mellon University Dickson Prize in Science (2008) och Japans Kyoto Prize (2008). Han valdes till New York Academy of Sciences (1980), US National Academy of Sciences (1980), American Academy of Arts and Sciences (1985), Institute of Combinatorics and Its Applications (1990), American Association for the Advancement of Science (1991), US National Academy of Engineering (1992), American Philosophical Society (1994), French Academy of Sciences (2002) och European Academy of Sciences (2004).