标题: 1985 理查德·卡普 [打印本页] 作者: shiyi18 时间: 2022-4-16 04:29 标题: 1985 理查德·卡普 Richard Karp
BIRTH:
January 3, 1935, Boston Massachusetts
EDUCATION:
AB, Harvard 1955; SM Harvard 1956; Ph.D., Harvard 1959, Applied Mathematics; and eight honorary degrees.
EXPERIENCE:
1959-1968 Research Staff Member, IBM Watson Research Center, Yorktown Heights, New York; 1964-1965 Visiting Associate Professor, Electrical Engineering, University of Michigan; 1968-1994 Professor of Computer Science and of Industrial Engineering and Operations Research, University of California, Berkeley; 1973-1975 Associate Chairman for Computer Science, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley; 1980-1994 Professor of Mathematics, University of California, Berkeley; 1985-1986 Co-chair, Program in Computational Complexity, Mathematical Sciences Research Institute, Berkeley; 1988-1995 Research Scientist, International Computer Science Institute, Berkeley, California; 1995-1999 Professor of Computer Science and Adjunct Professor of Molecular Biotechnology, University of Washington; 1999- University Professor, University of California, Berkeley, Computer Science, Mathematics, and Bioengineering; 1999- Research Scientist, International Computer Science Institute, Berkeley, California; 2001-2003 Chair, Board of Governors, Institute for Mathematics and Its Applications; 2001-2004 Founding Chair, Section 34, National Academy of Sciences.
HONORS AND AWARDS:
Lanchester Prize in Operations Research, 1977 (co-winner); Fulkerson Prize in Discrete Mathematics, 1979; Miller Research Professor, Berkeley, 1980-81; Faculty Research Lecturer, Berkeley, 1981-82; Einstein Fellowship and Lady Davis Fellowship, Technion, Haifa, Israel, 1983; ACM Turing Award, 1985; Distinguished Teaching Award, University of California at Berkeley, 1986; Doctor of Science (honoris causa), University of Pennsylvania, 1986; John von Neumann Lecturer, SIAM, 1987; Doctor of Science (honoris causa), Technion, 1989; Class of 1939 Chair, University of California at Berkeley, 1989; ORSA/TIMS von Neumann Theory Prize, 1990; Doctor of Science (honoris causa), University of Massachusetts, 1990; Doctor of Humane Letters (honoris causa), Georgetown University, 1992; Babbage Prize, 9th International Parallel Processing Symposium 1995; National Medal of Science, 1996; Centennial Medal, Harvard University, 1997; Kyoto Prize, 2008; Harvey Prize; Benjamin Franklin Medal.
RICHARD ("DICK") MANNING KARP DL Author Profile link
United States – 1985
CITATION
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.
SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
VIDEO INTERVIEW
Richard Karp was born in Boston, Massachusetts on January 3, 1935. He attended Boston Latin School, and received the A.B, S.M. and Ph.D. degrees in Mathematics and Applied Mathematics from Harvard University in 1955, 1956 and 1959.
Karp then joined the research staff of the IBM Watson Research Center in Yorktown Heights, NY, where he worked until 1968. During that time, Karp did foundational work on models of parallel computation, which involves the simultaneous use of multiple coordinated computers to solve a single problem. Roughly twenty years later, he returned to the study of parallel computation and continues to work in that area.
Karp discusses his nine years at IBM’s Watson Research Center and the work he did there on algorithm design and the mathematics of vector addition systems.
Motivated by the desire to teach and "to be where the action is," in 1968 Karp moved to the University of California, Berkeley, with appointments in Computer Science and in Operations Research. His dedication to teaching won him the UC Berkeley Distinguished Teaching Award in 1986.
Karp's initial research at Berkeley focused on heuristic algorithms for hard combinatorial problems, particularly for the notoriously difficult Traveling Salesmen Problem (TSP). Like many combinatorial problems, there was no efficient TSP algorithm that could be proved correct for all input, and whose worst-case running time is bounded by a polynomial function of the input size. Also lacking was an explanation of why an efficient algorithm had been so elusive.
Karp explains the difference between P (polynomial time) and NP (nondeterministic polynomial time) algorithmic complexity classes.
In one of the most significant paper of his career, Karp's 1972 Reducibility Among Combinatorial Problems provided a convincing explanation for the elusiveness of an efficient solution. In that seminal paper, Karp expanded on the concept (first introduced by Stephen Cook in 1971, and independently by Leonid Levin) of NP-completeness and proved that if any of twenty-one well-known difficult problems (including TSP) could be solved by an efficient algorithm, then all of the problems could be efficiently solved. NP-completeness shows, in an important sense, that these 21 problems are all equivalent. The collective failure by many talented people to find efficient algorithms for specific NP-complete problems strongly suggests that no efficient algorithm exists for any of them. Importantly, the paper established a framework for adding additional problems to the class of NP-complete problems, which has since grown to include many thousands. Today, only one or two classic combinatorial problems remain unclassified as to whether they are NP-complete or not. While most of the classified classic problems are NP-complete, several have been shown to be efficiently solvable.
Karp recounts his formulation of the P=NP question while writing the paper “Reducibility Among Combinatorial Problems” (1972).
Karp's work on NP-completeness substantially motivated the discussion of the famous unsolved P = NP question and its further examination by mathematicians and computer scientists. In essence, P = NP asks whether finding a solution to a problem is inherently more difficult than verifying that a proposed solution is correct. Not only is the problem considered the most important open question in theoretical computer science, it is also one of the most important open questions in mathematics.
The year after his paper on NP-completeness, Karp co-authored with Jack Edmonds and John Hopcroft (himself a Turing Award recipient) two very significant papers on efficient algorithms for network flow and bipartite graph matching. The network flow problem is to compute the maximum steady-state amount of material (for example, liquids in a pipe or bits in a communication network) that can be transported from a source to a destination in a network, where each edge (pipe, wire, road etc.) in the network can have a different but bounded capacity. This is one of the most widely studied problems in optimization and algorithmic computer science, and is not limited to physical networks as the same problems arise in, for example, biological cycles. The bipartite matching problem is a particularly useful special case of network flow that has a huge number of non-physical applications. Karp and Hopcroft showed in 1973 that the bipartite matching problem can be solved more efficiently than the general network flow problem [4] .
Another major theme in Karp's research has been the use of probability in both the design and analysis of efficient algorithms. Karp's interest in the probabilistic analysis of algorithms began in the 1980s, when he examined questions of the average, rather than the worst-case, running times of particular algorithms. In probabilistic analysis, the algorithm is fixed and deterministic, but its input is assumed to be drawn from a space universe of possible inputs according to a well-specified probabilistic model. The analysis finds the expected running time (or other characteristic) for that distribution of inputs. Karp later became active in the design of randomized algorithms, where the algorithm itself, rather than the input to the algorithm, has a random component. Surprisingly, randomizing the behavior of an algorithm can often significantly reduce its expected running time for any input.
Karp describes his work on the probabilistic analysis of algorithms, focusing on average rather than worst-case complexity.
Karp's most recent research has been in computational biology. This work began in the 1990s, as the field began to grow rapidly under the influence of the Human Genome Project. Karp first examined physical mapping of genes, devising algorithms to help determine the physical location of genes in a genome given the limited indirect experimental information about gene location. Such algorithms were especially important before affordable full DNA sequencing became available. From that beginning, Karp has examined a wide range of algorithmic issues in biology, such as:
determining protein interactions
designing and analyzing methods for gene mapping under different data collection technologies
designing and analyzing methods for problems that arise in population genetics and family pedigree analysis
finding repeating patterns and structures in gene sequences
constructing and analyzing networks that represent biological interactions, such as protein-protein contact, gene regulation, and metabolic pathways.
Much of Karp's work in computational biology uses techniques from combinatorial optimization, but more recently his work has also involved stochastic approaches from the field of machine learning. A new direction for Karp, this recent work on machine learning is related to his continuing interest in the use of probability in the design of algorithms and in the analysis of algorithmic behavior.
Karp describes his mid-career shift to apply his combinatorial expertise in the emerging field of computational biology.
In 1995 Karp left Berkeley for the Department of Computer Science at the University of Washington, where he was also an Adjunct Professor of Molecular Biotechnology. He returned to Berkeley in 1999 with appointments in Computer Science, Mathematics, and Bioengineering.
In addition, Karp is a Senior Research Scientist at the International Computer Science Institute in Berkeley, and was a principal in the creation of the Institute. Karp is currently a University Professor at the University of California, a prestigious title that has been awarded only thirty-eight times. Other major awards include election to the National Academy of Sciences in 1980, election to the National Academy of Engineering in 1992, the U.S. National Medal of Science in 1996, and the Kyoto Prize in 2008.
During his years at Berkeley and Washington, Karp mentored almost forty Ph.D. students. In addition to his professional accomplishments, Karp is an avid reader and chess player.
