Uit Wikipedia, de vrije encyclopedie
Richard M. Karp
(
Boston
,
3 januari
1935
) is een
Amerikaans
informaticus aan de
universiteit van Berkeley
. Voor zijn bijdragen aan de
complexiteitstheorie
kreeg hij in 1985 de
Turing Award
.
Karp werd op 3 januari 1935 geboren in Boston en ging naar de
Boston Latin School
. Hij studeerde aan de
Harvard-universiteit
en promoveerde daar in 1959 in de toegepaste wiskunde. Tussen 1959 en 1968 werkte hij bij de onderzoeksafdeling van
IBM
.
Zijn belangrijkste wetenschappelijke bijdragen deed Karp in de periode van 1968 tot 1994 als hoogleraar aan de Universiteit van Californie in Berkeley. Van 1994 tot 1999 was hij hoogleraar aan de
Universiteit van Washington
, waarna hij als universiteitshoogleraar terugkeerde in Berkeley.
Karp heeft belangrijke bijdragen geleverd aan de complexiteitstheorie en
operationeel onderzoek
. Tegenwoordig houdt hij zich vooral bezig met
bio-informatica
.
In 1972 publiceerde hij het artikel
Reducability among Combinatorial Problems
,
[2]
waarin hij van 21
beslissingsproblemen
bewees dat ze
NP-volledig
zijn, door het
vervulbaarheidsprobleem
, direct en indirect, naar hen te reduceren. Hiermee gaf hij een belangrijke impuls aan het bestuderen van de
complexiteitsklasse NP
en de vraag of de complexiteitsklassen
P
en NP gelijk zijn.
Karp was mede-ontdekker van het
Edmonds-Karp-algoritme
om de maximale stroom in grafen te bepalen (1971), het
Hopcroft-Karp-algoritme
om de grootste onafhankelijke kantenverzameling van
bipartiete grafen
te bepalen (1980) en het
Rabin-Karp-algoritme
voor zoeken in
strings
(1987).
In 1980 bewees Karp samen met
Richard Lipton
de
Karp-Lipton-stelling
, die zegt dat als het zo is dat het vervulbaarheidsprobleem kan worden opgelost door
booleaanse circuits
van
polynomiale
grootte, dan de
polynomiale hierarchie
samenvalt met het tweede niveau.
Voor zijn werk in de complexiteitstheorie kreeg Karp in 1985 een
Turing Award
en in 1996 een
National Medal of Science
.
Bronnen, noten en/of referenties
|
1966:
Alan J. Perlis
·
1967:
Maurice V. Wilkes
·
1968:
Richard Hamming
·
1969:
Marvin Minsky
·
1970:
J.H. Wilkinson
·
1971:
John McCarthy
·
1972:
Edsger Dijkstra
·
1973:
Charles W. Bachman
·
1974:
Donald E. Knuth
·
1975:
Allen Newell
,
Herbert Simon
·
1976:
Michael Rabin
,
Dana S. Scott
·
1977:
John Backus
·
1978:
Robert W. Floyd
·
1979:
Kenneth E. Iverson
·
1980:
Tony Hoare
·
1981:
Edgar F. (Ted) Codd
·
1982:
Stephen A. Cook
·
1983:
Ken Thompson
,
Dennis M. Ritchie
·
1984:
Niklaus Wirth
·
1985:
Richard M. Karp
·
1986:
John Hopcroft
,
Robert Tarjan
·
1987:
John Cocke
·
1988:
Ivan Sutherland
·
1989:
William Kahan
·
1990:
Fernando J. Corbato
·
1991:
Robin Milner
·
1992:
Butler Lampson
·
1993:
Juris Hartmanis
,
Richard E. Stearns
·
1994:
Edward Feigenbaum
,
Raj Reddy
·
1995:
Manuel Blum
·
1996:
Amir Pnueli
·
1997:
Douglas Engelbart
·
1998:
Jim Gray
·
1999:
Frederick P. Brooks, Jr.
·
2000:
Andrew Chi-Chih Yao
·
2001:
Ole-Johan Dahl
,
Kristen Nygaard
·
2002:
Ron Rivest
,
Adi Shamir
,
Leonard M. Adleman
·
2003:
Alan Kay
·
2004:
Vinton G. Cerf
,
Robert E. Kahn
·
2005:
Peter Naur
·
2006:
Frances E. Allen
·
2007:
Edmund M. Clarke
,
E. Allen Emerson
,
Joseph Sifakis
·
2008:
Barbara Liskov
·
2009:
Charles Thacker
·
2010:
Leslie Valiant
·
2011:
Judea Pearl
·
2012:
Shafi Goldwasser
,
Silvio Micali
·
2013:
Leslie Lamport
·
2014:
Michael Stonebraker
·
2015:
Martin Hellman
,
Whitfield Diffie
·
2016:
Tim Berners-Lee
·
2017:
John L. Hennessy
,
David Patterson
·
2018:
Yoshua Bengio
,
Geoffrey Hinton
,
Yann LeCun
·
2019:
Patrick M. Hanrahan
,
Edwin E. Catmull
·
2020:
Alfred Aho
,
Jeffrey Ullman
·
2021:
Jack Dongarra
·
2022:
Robert Metcalfe
·
2023:
Avi Wigderson