Dr. Karp has made fundamental contributions to the development of the theory of computational complexity which began in the early 1970s by establishing the theory of NP-completeness, having a profound influence on the guiding principles for analysis and design of algorithms. He has also developed many practically relevant computer algorithms.
The traveling-salesman problem and minimum spanning trees: Part II (Held, M. and Karp, R.). Mathematical Programming 1: 6-25, 1971.
Reducibility among Combinatorial Problems (Miller, R. E. and Thatcher, J. W. eds.). in Proceedings of Complexity of Computer Computations, Plenum Press, New York, 85-103, 1972.
Theoretical improvements in algorithmic efficiency for network flow problems (Edmonds, J. and Karp, R.). Journal of the ACM 19: 248-264, 1972.
Random walks, universal traversal sequences, and the complexity of maze problems (Aleliunas, R., Karp, R. M., Lipton, R., Lovász, L. and Rackoff, C.). 20th Annual Symposium on Foundations of Computer Science : 218-223, 1979.
A fast parallel algorithm for the maximal independent set problem (with Wigderson, A.). Journal of the ACM 32: 762-773, 1985.
Conserved pathways within bacteria and yeast as revealed by global protein network alignment (Kelley, B. P., Sharan, R., Karp, R. M., Sittler, T., Root, D. E., Stockwell, B. R.,and Ideker, T). Proceedings of the National Academy of Sciences 100: 11394-11399, 2003.
Dr. Richard Manning Karp has made fundamental contributions to the development of the theory of computational complexity which began in the early 1970s by establishing the theory of NP-completeness, having a profound influence on the guiding principles for analysis and design of algorithms. He has also developed many practically relevant computer algorithms.
Dr. Karp established the theory of NP-completeness by creating a technique for measuring the computational complexity of combinatorial problems by establishing complexity classes of equally hard-to-solve problems in accordance with the concept of polynomial-time reduction, and determining the class to which each problem would belong. With this achievement, he revealed that many optimization problems in operation research and various problems in areas related to computer science are equally hard-to-solve problems belonging to the NP-complete class. He also deduced and disseminated a standard methodology for this process, making a dramatic leap in the theory of computation and algorithms that underpin computer science.
The establishment of the theory of NP-completeness not only added a new page to human wisdom by bringing computational complexity within the scope of scientific research, as symbolized by the problem referred to as the “P versus NP problem”, which is an open problem of central interest in both communities of computer science and mathematics, but also accelerated the development of algorithm engineering and had a significant influence on the guiding principles for the evaluation and design of algorithms for various problems existing in technological fields. Before his pioneering contributions, algorithms had to be designed individually for each of a plethora of technological problems. Dr. Karp freed the algorithm design from this condition of manual labor and elevated it to a scientific technology.
In addition to these achievements, Dr. Karp has developed numerous algorithms with practical relevance, the most notable being the Edmonds-Karp algorithm. He built a hub of study of the theoretical computer science centered at the University of California, Berkeley, where he mentored many young researchers, thereby playing a leading role in the establishment of the theories of parallel algorithms and probabilistic algorithms. Over the last decade, based on his belief that computer scientists should work on research themes that are useful to other academic fields, particularly the life science, he has made significant contributions to the study of algorithms in the bioinformatics field.
For these reasons, the Inamori Foundation is pleased to present the 2008 Kyoto Prize in Advanced Technology to Dr. Richard Manning Karp.
Thanks to the sacrifices of my parents my three siblings and I had the benefit of a good education. Mathematics was my first love, and within mathematics I was drawn especially to algorithms. An algorithm is a step-by-step procedure for solving a computational problem. Familiar to all of us are the algorithms for arithmetic that we learned in school.
Algorithms underlie every application of information technology. Search engines use algorithms to answer our queries for information, and the Internet uses an algorithm to transmit messages to their destinations. Electronic commerce depends on a simple, elegant algorithm for encrypting data to ensure privacy.
As a child I entertained my friends by multiplying four-digit numbers in my head, using an algorithm that I had devised. Later, I designed an algorithm to schedule the classes at the school where my father taught mathematics.
A good algorithm must efficiently give a correct result. The efficiency of an algorithm is measured primarily by the number of computation steps it requires.@I have developed efficient algorithms for practical problems such as computing the fastest rate at which information can flow to a destination within a network, or detecting repeated patterns within large bodies of data.@But the work for which I am best known is aimed at showing that some problems are so difficult that no efficient algorithms exist for their solution. Such problems, which are known as NP-complete problems, arise in virtually every area of application. The phenomenon of NP-completeness made workers in many fields aware that like the physical sciences, computer science has fundamental limits, governing the inherent complexity of computation.
I am grateful to live at a time when I have been able to contribute to society by exploring the subject I love most. I am grateful for the example my parents set for me, and I find the greatest reward in the friendship and support of the many students, colleagues and friends who have shared my adventures in research.