Newtonpedia ES
Home › Computing › Richard M. Karp
Richard M. Karp
Image: Wikimedia Commons

Richard M. Karp

American computer scientist known for the theory of algorithms and computational complexity · 1935

Born
January 3, 1935
Country
United States
Section
Computing
Awards
Turing Award

Biography

Richard Manning Karp is an American computer scientist whose work on the theory of algorithms and computational complexity earned him the Turing Award in 1985. Born in Boston in 1935, he helped establish which problems a computer can solve quickly and which become impractical as they grow. Several algorithms bearing his name are now standard material in any introductory computer science course.

Karp was born in Boston, Massachusetts, into a Jewish family. He grew up in a small apartment in Dorchester, a neighbourhood that was then largely Jewish. Both of his parents were Harvard graduates; his mother earned her degree at the age of 57 after attending evening classes, while his father had hoped to become a doctor but became a mathematics teacher because he could not afford medical school. Karp has three younger siblings: Robert, David and Carolyn.

He studied at Harvard, earning his bachelor's degree in 1955, his master's in 1956 and his PhD in applied mathematics in 1959. He then joined IBM's Thomas J. Watson Research Center, where he worked on optimisation, the search for the best solution among many possible ones. In 1968 he became a professor at the University of California, Berkeley, with appointments in computer science, mathematics and operations research. He spent four years teaching at the University of Washington, but returned to Berkeley and has remained there since.

The core of his work is the theory of algorithms. An algorithm is a sequence of steps that solves a problem, and the theory asks how much time a computer needs to run it as the problem gets larger. In 1971, together with Jack Edmonds, he developed a method for finding the maximum flow through a network, that is, how much can move through a system of pipes or roads without exceeding the capacity of any section. It is known as the Edmonds-Karp algorithm.

His most cited contribution came in 1972, when he published the paper "Reducibility Among Combinatorial Problems". In it he showed that 21 classic problems belong to the NP-complete class: a group for which no method is known that runs quickly on every input, and whose members are equivalent, so that a fast method for any one of them would work for all. The paper built on earlier work by Stephen Cook on the same class and gave the question of P versus NP a concrete and highly influential form. In 1980, together with Richard J. Lipton, he proved a result linking Boolean circuits to the polynomial hierarchy, a way of ranking problems by difficulty.

Karp also collaborated widely. In 1962, with Michael Held, he developed the Held-Karp algorithm for the travelling salesman problem, which seeks the shortest route that visits a set of cities. In 1973, with John Hopcroft, he published the Hopcroft-Karp algorithm for finding maximum matchings in bipartite graphs, still regarded as the fastest known method for this task. In 1987, with Michael O. Rabin, he created the Rabin-Karp algorithm for searching text, which compares numerical fingerprints rather than characters one by one.

In recent years his attention has turned to bioinformatics, where algorithmic methods help analyse DNA sequences and large volumes of biological data. Beyond the Turing Award, his honours include the 2004 Benjamin Franklin Medal, the 2008 Kyoto Prize, and membership of the US National Academy of Engineering since 1992. In 2012 he became the founding director of the Simons Institute for the Theory of Computing at Berkeley.

His legacy lies at the foundation of modern theoretical computer science. The classification he proposed in 1972 still guides researchers and engineers deciding which tasks can be tackled exactly and which need approximate methods. Many of his algorithms appear in programming textbooks, and his list of NP-complete problems remains a standard starting point for the study of complexity.

Main contributions

  • 1962Held-Karp algorithm: an exact method for the travelling salesman problem, which seeks the shortest route between several cities.
  • 1971Edmonds-Karp algorithm: a procedure for calculating the maximum flow that can pass through a network.
  • 1972List of 21 NP-complete problems: a demonstration that several classic problems are equivalent in difficulty.
  • 1973Hopcroft-Karp algorithm: a fast method for finding maximum matchings in bipartite graphs.
  • 1980Karp-Lipton theorem: a result linking Boolean circuits to the polynomial hierarchy of complexity.
  • 1987Rabin-Karp algorithm: a technique for searching strings of text by comparing numerical fingerprints.

Teachers and students

Studied under:

Anthony Oettinger

Taught:

Narendra KarmarkarSally FloydRajeev MotwaniPrabhakar Lakshman RagdeJean-Louis GoffinGeorge W. Hartzell, IIIDaniel FasuloLee Aaron NewbergYsmar Vianna Silva-FilhoPedro Gonzalo GazmuriRubin JohnsonAnne Ginzton CottrellRobert Malcolm MacGregorJames Powell RichardsonJonathan Alexander FrankleHoward Jeffrey KarloffManikandan NarayananSandra S. IraniEunice E. SantosLisa HellersteinYanjun ZhangAbhijit SahayAmoolya Hardev SinghNorm ZadaBarbara SimonsNoam NisanMichael LubyRaymond ReiterEric P. XingFaith EllenValerie KingRon ShamirDan GusfieldThomas Jerome SchaeferPhillip GibbonsKellogg S. BoothAndrés Weintraub PohorilleRobert M. KellerKathleen Marie O'HaraSukhamay KunduDanny Soroker

See their academic family tree →

Trivia and anecdotes

A family of graduates

Both of his parents graduated from Harvard, and his mother earned her degree at 57 after attending evening classes.

A father who could not become a doctor

His father wanted to study medicine but could not afford the fees and became a mathematics teacher instead.

Related discoveries and inventions

  • 1973
    Hopcroft–Karp algorithmAn algorithm that finds the largest possible matching in a bipartite graph, meaning the maximum number of pairs with no element used twice.
  • 1987
    Rabin–Karp algorithmAn algorithm that finds a pattern of characters in a text by first comparing numerical fingerprints (hash values) and checking letter by letter only when they match.

Their contemporaries

While Richard M. Karp was alive (1935–)…

Alive at the same time

Discovered or invented in those years

  • 1945
    ComputerA programmable machine that takes in data, processes it by following stored instructions, and produces results, able to switch tasks simply by running different software.
  • 1957
    Artificial satelliteAn artificial satellite is a human-made object placed in orbit around a celestial body, usually Earth, to collect information, relay signals, or carry out a specific task.
  • 1969
    InternetA global network of interconnected computer networks that communicate using the TCP/IP protocol suite.
  • 1971
    EmailA network service that lets users send and receive digital messages through addressed mailboxes, much like postal mail but electronic.
  • 1973
    Mobile phoneA handheld wireless phone that lets people make and receive calls while moving across a cellular network area.
  • 1989
    World Wide WebA system of linked documents and resources, connected by hyperlinks and accessed over the Internet with web browsers.

See this life on the timeline →

More people in Computing