Richard M. Karp

Last updated
Richard Manning Karp
Karp mg 7725-b.cr2.jpg
Richard Karp at the EPFL on 13th of July 2009
Born (1935-01-03) January 3, 1935 (age 89)
Boston, Massachusetts, US
NationalityAmerican
Alma mater Harvard University
Known for Aanderaa–Karp–Rosenberg conjecture
Edmonds–Karp algorithm
Held–Karp algorithm
Hopcroft–Karp algorithm
Karmarkar–Karp algorithm
Rabin–Karp string search algorithm
Karp–Lipton theorem
Karp's 21 NP-complete problems
Vector addition system
Awards Fulkerson Prize (1979)
Turing Award (1985)
John von Neumann Theory Prize (1990)
IEEE Computer Society Charles Babbage Award (1995)
National Medal of Science (1996)
Harvey Prize (1998)
EATCS award (2000)
Benjamin Franklin Medal (2004)
Kyoto Prize (2008)
Scientific career
Fields Computer Science
Institutions University of California, Berkeley
IBM
Thesis Some Applications of Logical Syntax to Digital Computer Programming (1959)
Doctoral advisor Anthony Oettinger [1]
Doctoral students

Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008. [2]

Contents

Karp was elected a member of the National Academy of Engineering (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, and Carolyn. His family was Jewish, [3] 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. [3] 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. Karp was the first associate chair of the Computer Science Division within the Department of Electrical Engineering and Computer Science. [4] Apart from a 4-year period as a professor at the University of Washington, 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, 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 was elected to the 2002 class of Fellows of the Institute for Operations Research and the Management Sciences. [5] He is the recipient of several honorary degrees and a member of the U.S. National Academy of Sciences, [6] the American Academy of Arts and Sciences, [7] and the American Philosophical Society. [8]

In 2012, Karp became the founding director of the Simons Institute for the Theory of Computing at the University of California, Berkeley. [9]

Work

Karp has made many important discoveries in computer science, combinatorial algorithms, and operations research. His major current research interests include bioinformatics.

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 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. [10]

In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, the fastest known method for finding maximum cardinality matchings in bipartite graphs.

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 [11] for the (1985) 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.

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

<span class="mw-page-title-main">Michael O. Rabin</span> Israeli mathematician and computer scientist

Michael Oser Rabin is an Israeli mathematician, computer scientist, and recipient of the Turing Award.

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout computer science are computationally intractable, and it drove interest in the study of NP-completeness and the P versus NP problem.

<span class="mw-page-title-main">Russell Impagliazzo</span> American computer scientist

Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.

<span class="mw-page-title-main">Vijay Vazirani</span> Indian American professor of computer science

Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.

<span class="mw-page-title-main">Jack Edmonds</span> American/Canadian mathematician and computer scientist

Jack R. Edmonds 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, polyhedral combinatorics, discrete mathematics and the theory of computing. He was the recipient of the 1985 John von Neumann Theory Prize.

<span class="mw-page-title-main">Michael Sipser</span> American theoretical computer scientist (born 1954)

Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the Dean of Science at the Massachusetts Institute of Technology.

Richard Jay Lipton 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 worked in computer science theory, cryptography, and DNA computing.

In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph.

Alistair Sinclair is a British computer scientist and computational theorist.

<span class="mw-page-title-main">3-dimensional matching</span>

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology.

Eugene Leighton (Gene) Lawler was an American computer scientist and a professor of computer science at the University of California, Berkeley.

<span class="mw-page-title-main">Noam Nisan</span> Israeli computer scientist

Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.

References

  1. 1 2 Richard M. Karp at the Mathematics Genealogy Project.
  2. ↑ Richard Manning Karp - THE 2008 KYOTO PRIZE - Advanced Technology
  3. 1 2 The Power and Limits of Algorithms Richard Manning Karp, Kyoto Prize Address, 2008
  4. ↑ Karp, Richard. "A Personal View of Computer Science at Berkeley". www2.eecs.berkeley.edu. Retrieved 1 December 2021.
  5. ↑ Fellows: Alphabetical List, Institute for Operations Research and the Management Sciences , retrieved 2019-10-09
  6. ↑ "Richard M. Karp". www.nasonline.org. Retrieved 2022-02-22.
  7. ↑ "Richard M. Karp". American Academy of Arts & Sciences. Retrieved 2022-02-22.
  8. ↑ "APS Member History". search.amphilsoc.org. Retrieved 2022-02-22.
  9. ↑ "California Chosen as Home for Computing Institute". The New York Times. 30 April 2012. Retrieved 23 October 2016.
  10. ↑ Richard M. Karp (1972). "Reducibility Among Combinatorial Problems" (PDF). In R. E. Miller; J. W. Thatcher (eds.). Complexity of Computer Computations. New York: Plenum. pp. 85–103.
  11. ↑ Association for Computing Machinery. "ACM Award Citation/Richard M. Karp". Archived from the original on 2012-07-03. Retrieved 2010-01-17.
Preceded by Benjamin Franklin Medal in Computer and Cognitive Science
2004		Succeeded by
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.