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

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

and computational theorist at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

. 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 the fi ...

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 organization, nonprofit, NGO, non-governmental organization. It is part of the National Academies of Sciences, Engineering, and Medicine (NASEM), along with the National Academ ...

(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 Boston is the capital and most populous city in the Commonwealth (U.S. state), Commonwealth of Massachusetts in the United States. The city serves as the cultural and Financial centre, financial center of New England, a region of the Northeas ...

, Karp has three younger siblings: Robert,

David David (; , "beloved one") was a king of ancient Israel and Judah and the third king of the United Monarchy, according to the Hebrew Bible and Old Testament. The Tel Dan stele, an Aramaic-inscribed stone erected by a king of Aram-Dam ...

, and Carolyn. His family was

Jewish Jews (, , ), or the Jewish people, are an ethnoreligious group and nation, originating from the Israelites of History of ancient Israel and Judah, ancient Israel and Judah. They also traditionally adhere to Judaism. Jewish ethnicity, rel ...

,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 university, private Ivy League research university in Cambridge, Massachusetts, United States. Founded in 1636 and named for its first benefactor, the History of the Puritans in North America, Puritan clergyma ...

, 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 mathematics, mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and Industrial sector, industry. Thus, applied mathematics is a ...

in 1959. He started working at

IBM International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...

's Thomas J. Watson Research Center. 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 and informally U-Dub or U Dub) is a public research university in Seattle, Washington, United States. Founded in 1861, the University of Washington is one of the oldest universities on the West Coast of the Uni ...

, 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 science, behavior ...

, and was the recipient of the

Harvey Prize The 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 – Israel Institute of Technology, Technion in Haifa. The prize has become a ...

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 title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned society, learned or professional society, p ...

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

. 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 Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often s ...

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

, the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (The Academy) 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, and other ...

, and the

American Philosophical Society The American Philosophical Society (APS) is an American scholarly organization and learned society founded in 1743 in Philadelphia that promotes knowledge in the humanities and natural sciences through research, professional meetings, publicat ...

. 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 An algorithm is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems. Broadly, algorithms define process(es), sets of rules, or methodologies that are to be f ...

, and

operations research Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...

. His major current research interests include

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

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

travelling salesman problem In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...

. In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the

maximum flow problem In Optimization (mathematics), 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 ...

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 published the Hopcroft–Karp algorithm, the fastest known method for finding maximum cardinality matchings in

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

s. In 1980, along with Richard J. Lipton, Karp proved the Karp–Lipton theorem (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 Test score, scoring have changed several times. For much of its history, it was called the Scholastic Aptitude Test ...

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

s with a polynomial number of

logic gate A logic gate is a device that performs 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 gate, one that has, for ...

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 operations researchers 1935 births Living people American theoretical computer scientists 1994 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 American scientists National Medal of Science laureates Turing Award laureates UC Berkeley College of Engineering faculty Members of the French Academy of Sciences Mathematicians 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 John A. Paulson School of Engineering and Applied Sciences alumni Members of the American Philosophical Society