The 2008 Laureates / Advanced Technology Category / Information Science

"Fundamental Contributions to the Development of the Theory of Computational Complexity "
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.

Fundamental Contributions to the Development of the Theory of Computational Complexity

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.