Richard Manning Karp (born January 3, 1935) is an American

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (a ...

and computational theorist at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant un ...

. He is most notable for his research in the theory of algorithms, for which he received a

Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...

in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the

Kyoto Prize The is Japan's highest private award for lifetime achievement in the arts and sciences. It is given not only to those that are top representatives of their own respective fields, but to "those who have contributed significantly to the scientific, ...

in 2008. Karp was elected a member of the

National Academy of Engineering The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of ...

(1992) for major contributions to the theory and application of NP-completeness, constructing efficient combinatorial algorithms, and applying probabilistic methods in computer science.

Biography

Born to parents Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert,

David David (; , "beloved one") (traditional spelling), , ''Dāwūd''; grc-koi, Δαυΐδ, Dauíd; la, Davidus, David; gez , ዳዊት, ''Dawit''; xcl, Դաւիթ, ''Dawitʿ''; cu, Давíдъ, ''Davidŭ''; possibly meaning "beloved one". w ...

, and Carolyn. His family was

Jewish Jews ( he, יְהוּדִים, , ) or Jewish people are an ethnoreligious group and nation originating from the Israelites Israelite origins and kingdom: "The first act in the long drama of Jewish history is the age of the Israelites""The ...

,The Power and Limits of Algorithms
Richard Manning Karp, Kyoto Prize Address, 2008 and he grew up in a small apartment, in a then mostly Jewish neighborhood of Dorchester in Boston. Both his parents were Harvard graduates (his mother eventually obtaining her Harvard degree at age 57 after taking evening courses), while his father had had ambitions to go to medical school after Harvard, but became a mathematics teacher as he could not afford the medical school fees. He attended

Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of highe ...

, where he received his bachelor's degree in 1955, his master's degree in 1956, and his Ph.D. in

applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemati ...

in 1959. He started working at IBM's

Thomas J. Watson Research Center The Thomas J. Watson Research Center is the headquarters for IBM Research. The center comprises three sites, with its main laboratory in Yorktown Heights, New York, U.S., 38 miles (61 km) north of New York City, Albany, New York and wit ...

. In 1968, he became professor of computer science, mathematics, and operations research at the

. Karp was the first associate chair of the Computer Science Division within the Department of Electrical Engineering and Computer Science. Apart from a 4-year period as a professor at the

University of Washington The University of Washington (UW, simply Washington, or informally U-Dub) is a public research university in Seattle, Washington. Founded in 1861, Washington is one of the oldest universities on the West Coast; it was established in Seatt ...

, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a research scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group. Richard Karp was awarded the

National Medal of Science The National Medal of Science is an honor bestowed by the President of the United States to individuals in science and engineering who have made important contributions to the advancement of knowledge in the fields of behavioral and social scienc ...

, 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 computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

. In 1994 he was inducted as a

Fellow A fellow is a concept whose exact meaning depends on context. In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements. Within the context of higher education ...

of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

. He was elected to the 2002 class of

s of the Institute for Operations Research and the Management Sciences. He is the recipient of several honorary degrees and a member of the U.S.

National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nat ...

, the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (abbreviation: AAA&S) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, a ...

, and the

American Philosophical Society The American Philosophical Society (APS), founded in 1743 in Philadelphia, is a scholarly organization that promotes knowledge in the sciences and humanities through research, professional meetings, publications, library resources, and communit ...

. In 2012, Karp became the founding director of the Simons Institute for the Theory of Computing at the

Work

Karp has made many important discoveries in computer science, combinatorial algorithms, and

operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...

. His major current research interests include

bioinformatics Bioinformatics () is an interdisciplinary field that develops methods and software tools for understanding biological data, in particular when the data sets are large and complex. As an interdisciplinary field of science, bioinformatics combi ...

. In 1962 he co-developed with Michael Held the Held–Karp algorithm, an exact exponential-time algorithm for the travelling salesman problem. In 1971 he co-developed with

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, po ...

the Edmonds–Karp algorithm for solving the maximum 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 1973 he and

John Hopcroft John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist. His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields. He is the IBM P ...

published the Hopcroft–Karp algorithm, the fastest known method for finding maximum cardinality matchings in

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V a ...

s. 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 gate A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic ga ...

s, then the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...

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 ''(1985)'' Turing Award was as follows:

References

External links

ACM Crossroads magazine interview/bio of Richard Karp

Biography of Richard Karp
from the Institute for Operations Research and the Management Sciences {{DEFAULTSORT:Karp, Richard American computer scientists American operations researchers 1935 births Living people Theoretical computer scientists Fellows of the Association for Computing Machinery Fellows of the Society for Industrial and Applied Mathematics Fellows of the Institute for Operations Research and the Management Sciences Kyoto laureates in Advanced Technology Members of the United States National Academy of Engineering Members of the United States National Academy of Sciences John von Neumann Theory Prize winners Jewish scientists Jewish American scientists National Medal of Science laureates Turing Award laureates UC Berkeley College of Engineering faculty Members of the French Academy of Sciences People from Boston 20th-century American engineers 21st-century American engineers 20th-century American mathematicians 21st-century American mathematicians 20th-century American scientists 21st-century American scientists Harvard School of Engineering and Applied Sciences alumni Members of the American Philosophical Society