Richard Manning Karp (born January 3, 1935) is an American computer scientist 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 u ...

. He is most notable for his research in the

theory of algorithms In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., ...

, 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 comput ...

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 high ...

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

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...

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 Seattl ...

, 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 The International Computer Science Institute (ICSI) is an independent, non-profit research organization located in Berkeley, California, United States. Since its founding in 1988, ICSI has maintained an affiliation agreement with the University ...

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 Harvey Prize is an annual Israeli award for breakthroughs in science and technology, as well as contributions to peace in the Middle East granted by the Technion in Haifa. History The prize is named for industrialist and inventor Leo Harvey. T ...

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 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. He was elected to the 2002 class of

s of the

Institute for Operations Research and the Management Sciences The Institute for Operations Research and the Management Sciences (INFORMS) is an international society for practitioners in the fields of operations research (O.R.), management science, and analytics. It was established in 1995 with the merger o ...

. He is the recipient of several honorary degrees and a member of the U.S. National Academy of Sciences, 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 The Simons Institute for the Theory of Computing at the University of California, Berkeley is an institute for collaborative research in theoretical computer science. History Established on July 1, 2012 with a grant of $60 million from the Simons ...

at the

Work

Karp has made many important discoveries in computer science,

combinatorial algorithms The following is a list of well-known algorithms along with one-line descriptions for each. Automated planning Combinatorial algorithms General combinatorial algorithms * Brent's algorithm: finds a cycle in function value iterations using on ...

, 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. In 1962 he co-developed with Michael Held the

Held–Karp algorithm The Held–Karp algorithm, also called Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Richard E. Bellman, Bellman and by Held and Richard M. Karp, Karp to solve the traveling salesman problem ( ...

, an exact exponential-time algorithm for the

travelling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...

. In 1971 he co-developed with Jack Edmonds the

Edmonds–Karp algorithm In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(, V, , E, ^2) time. The algorithm was first published by Yefim Dinitz (whose name is also ...

for solving the

maximum flow problem In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such ...

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 In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of ...

, the fastest known method for finding maximum cardinality matchings in bipartite graphs. In 1980, along with

Richard J. Lipton Richard Jay Lipton (born September 6, 1946) is an American computer scientist who is Associate Dean of Research, Professor, and the Frederick G. Storey Chair in Computing in the College of Computing at the Georgia Institute of Technology. He has ...

, Karp proved the

Karp–Lipton theorem In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then :\Pi_2 = \Sigma_2 \, and therefore \mathrm = \Sigma_2. \, ...

(which proves that if

SAT The SAT ( ) is a standardized test widely used for college admissions in the United States. Since its debut in 1926, its name and scoring have changed several times; originally called the Scholastic Aptitude Test, it was later called the Schol ...

can be solved by

Boolean circuit In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inp ...

s with a polynomial number of logic gates, 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 Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli mathematician and computer scientist and a recipient of the Turing Award. Biography Early life and education Rabin was born in 1931 in ...

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