Richard Manning Karp amerikansk matematiker og datalogi

Richard Manning Karp, (født 3. januar 1935, Boston, Mass., USA), amerikansk matematiker og datalogiker og vinder af 1985 AM Turing Award, den højeste ære inden for datalogi, for “hans fortsatte bidrag til teorien om algoritmer, herunder udvikling af effektive algoritmer til netværksstrøm og andre kombinatoriske optimeringsproblemer, identifikation af polynomitid-beregbarhed med den intuitive opfattelse af algoritmisk effektivitet og mest bemærkelsesværdigt bidrag til teorien om NP-fuldstændighed. ” Hans forskningsinteresser har inkluderet teoretisk computervidenskab, kombinatoriske algoritmer, diskret sandsynlighed, beregningsbiologi og internetalgoritmer.

Karp fik en bachelorgrad (1955), en kandidatgrad (1956) og en doktorgrad (1959), alt i matematik, fra Harvard University. Efter at have afsluttet sine studier arbejdede han som matematiker hos IBM (1959-68), før han flyttede til akademia. Karp havde stillinger ved University of California, Berkeley (1968–94), University of Washington (1995–99), og igen ved Berkeley (1999–), hvor han vendte tilbage som universitetsprofessor.

Karps papir fra ”Reducibility Among Combinatorial Problems” fra 1972 beviste, at mange ofte studerede kombinatoriske problemer er varianter af det samme problem, hvilket antyder, at de alle sandsynligvis er ufravigelige (NP-komplette problemer - det vil sige problemer, som ingen effektiv løsningsalgoritme er kendt). Karp er forfatteren af ​​Complexity of Computation (1974) og har patent på en type skiftende netværk med flere forbindelser.

Foruden Turing Award modtog Karp Fulkerson-prisen i diskret matematik (1979), US National Medal of Science (1996), Harvard University Centennial Medal (1997), Israel Institute of Technology Harvey Prize (1998), the Carnegie Mellon University Dickson Prize in Science (2008) og Japans Kyoto Prize (2008). Han blev valgt til 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) og European Academy of Sciences (2004).