Advanced Technology Category

Prize Field: Information Science

Richard Manning Karp
Computer Scientist

Affiliation: University of California, Berkeley; Senior Research Scientist, International Computer Science Institute
Title: University Professor
Date of Birth: January 3, 1935
Nationality: U.S.A.

Background: Dr. Karp has made fundamental contributions to the theory of computational complexity, which he began developing in the early 1970s by establishing the theory of NP-completeness. In addition to creating many practical computer algorithms of his own, Dr. Karp's work has exerted profound influence on the guiding principles behind the analysis and design of algorithms used in many scientific disciplines.

Fundamental Contributions to the Development of the Theory of Computational Complexity

The 2008 Kyoto Prize in Advanced Technology focuses on the field of Information Science. Richard Manning Karp will receive the award for his fundamental contributions to the development of the Theory of Computational Complexity.

Profile | Citation | Back to Laureates

Dr. Richard Manning Karp has made fundamental contributions to the development of the theory of computational complexity. He began in the early 1970s by establishing the theory of NP-completeness, which has had a profound influence on the guiding principles for analysis and design of algorithms. He has also developed many practically relevant computer algorithms.

In particular, Dr. Karp created 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. In more concrete terms, Dr. Karp established the theory of NP-completeness by defining the complexity class P as problems for which polynomial-time algorithms of deterministic solutions exist, the complexity class NP as problems for which polynomial-time algorithms of non-deterministic solutions exist, and the NP-complete, which is a subclass of the complexity class NP to which the hardest-to-solve problems belong. With this achievement, he revealed that many familiar problems which often appear in a wide range of optimization problems in operation research, and 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.

Among researchers of the theory of computation, the issue of whether complexity class P and complexity class NP are the same class or not is referred to as the "P versus NP problem", which is an open problem of central interest in computer science, having also caught the interest of the mathematical community. As indicated by this fact, Dr. Karp not only added a new page to human wisdom by bringing computational complexity within the scope of scientific research, 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 many of the problems extant in technological fields. Before his pioneering contributions, algorithms had to be designed individually for each of a plethora of technological problems. Dr. Karp freed 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 individual algorithms with practical relevance, the most notable being the Edmonds-Karp algorithm. He played a central role in the development of computational complexity theory, which has made notable advances since the early 1970s. Additionally, he built a framework for the study of theoretical computer science at the University of California, Berkeley where he held a professorship and mentored many young researchers, thereby playing a leading role in the establishment of the theories of parallel and probabilistic algorithms. Over the last decade, he has stayed true to his belief that computer scientists should work on research themes that are useful to other academic fields, particularly the life sciences, thereby making significant contributions to the study of algorithms in the bioinformatics field.