Richard Karp


Richard Karp

Infobox_Scientist
name = Richard Manning Karp


image_width =
caption =
birth_date = January 3, 1935
birth_place = Boston, Massachusetts
death_date =
death_place =
residence =
citizenship =
nationality = American
ethnicity =
field = Computer Science
work_institution = IBM
University of California, Berkeley
University of Washington
alma_mater =
doctoral_advisor =
doctoral_students = at the [http://www.genealogy.math.ndsu.nodak.edu/id.php?id=25275&fChrono=1 Mathematics Genealogy Project]
known_for = Edmonds-Karp algorithm
author_abbreviation_bot =
author_abbreviation_zoo =
prizes = Turing Award
National Medal of Science
Benjamin Franklin Medal
Kyoto Prize
religion =
footnotes =

Richard Manning Karp (born 1935) is a computer scientist and computational theorist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985 and the Kyoto Prize in 2008. [http://www.inamori-f.or.jp/laureates/k24_a_richard/prs_e.html]

Biography

Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. He attended Harvard University, where he received his Bachelor's degree in 1955, his Master's degree in 1956, and his Ph.D. in applied mathematics in 1959.

He started working at IBM's Thomas J. Watson Research Center. In 1968, he became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley.

Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees.

Work

He has made many other important discoveries in computer science and operations research in the area of combinatorial algorithms. His major current research interests include bioinformatics.

Edmonds-Karp algorithm

In 1971 he co-developed with Jack Edmonds the Edmonds-Karp algorithm for solving the max-flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 Problems to be NP-complete.

In 1980, along with Richard J. Lipton, Karp proved the Karp-Lipton theorem (which proves that, if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level).

In 1987 he co-developed with Michael O. Rabin the Rabin-Karp string search algorithm.

Turing Award

His citation for the Turing Award was as follows:

:"For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult."

References

External links

* [http://www.acm.org/crossroads/dayinlife/bios/richard_karp.html ACM Crossroads magazine interview/bio of Richard Karp]
* [http://www.cs.berkeley.edu/People/Faculty/Homepages/karp.html Karp's Home Page at Berkeley]
* [http://www.genealogy.ams.org/html/id.phtml?id=25275 American Mathematical Society Genealogy for Richard Karp]

Persondata
NAME= Karp, Richard Manning
ALTERNATIVE NAMES=
SHORT DESCRIPTION= American computer scientist
DATE OF BIRTH= 1935
PLACE OF BIRTH= Boston, Massachusetts
DATE OF DEATH=
PLACE OF DEATH=


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Richard Karp — Richard Manning Karp, né en 1935 à Boston dans le Massachusetts, est un informaticien américain, connu pour ses recherches en théorie de la complexité. Il a reçu le prix Turing en 1985 pour ces travaux. Né de Abraham et Rose Karp à Boston, Karp a …   Wikipédia en Français

  • Richard Karp — Saltar a navegación, búsqueda Richard Karp Richard Manning Karp (Boston, (Estados Unidos), 3 de enero de 1935) es un científico de la computación, conocido por su investigación en teoría de algoritmos, por lo que recibió el …   Wikipedia Español

  • Richard Karp — ist der Name folgender Personen: Richard A. Karp (* 1944), amerikanischer Informatiker Richard M. Karp (* 1935), amerikanischer Informatiker Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeichne …   Deutsch Wikipedia

  • Richard M. Karp — Richard Karp Richard Karp, né en 1935 à Boston dans le Massachusetts, est un informaticien américain, connu pour ses recherches en théorie de la complexité. Il a reçu le prix Turing en 1985 pour ces travaux. Né de Abraham et Rose Karp à …   Wikipédia en Français

  • Richard M. Karp — Richard Karp 2009 Richard Manning Karp (* 3. Januar 1935 in Boston, Massachusetts) ist ein amerikanischer Informatiker. Er ist verantwortlich für bedeutende Erkenntnisse in der Komplexitätstheorie. 1985 erhielt er für seine Forschungsarbeit auf… …   Deutsch Wikipedia

  • Karp — may refer to:People*Barrie Karp (born 1945), U.S. philosopher and visual artist *Bob Karp (1911 mdash;1975), U.S. comics writer *Carol Karp (1926 mdash;1972), U.S. mathematician, professor at the University of Maryland. *David Karp (1922… …   Wikipedia

  • Richard W. Hamming — Richard Hamming Richard Hamming Nom de naissance Richard Wesley Hamming Naissance 11 février 1915 Chicago (Illinois) Décès 7 janvier 1998 (à 72 ans) Monterey (Californie) Nationalité …   Wikipédia en Français

  • Richard Wesley Hamming — Richard Hamming Richard Hamming Nom de naissance Richard Wesley Hamming Naissance 11 février 1915 Chicago (Illinois) Décès 7 janvier 1998 (à 72 ans) Monterey (Californie) Nationalité …   Wikipédia en Français

  • Richard Hamming — Naissance 11 février 1915 Chicago (Illinois) Décès 7 janvier 1998 (à 82 ans) Monterey (Californie) Nationalité …   Wikipédia en Français

  • Richard E. Stearns — Richard Stearns Pour les articles homonymes, voir Stearns. Richard Edwin Stearns (né le 5 juillet 1936) est un informaticien qui, avec Juris Hartmanis, a reçu en 1993 le prix Turing pour leurs recherches communes sur les bases de la théorie de la …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.