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.

Computer scientist who made fundamental contributions to the development of the theory of computational complexity

Dr. Richard M. Karp has had a profound influence on the guiding principles for analysis and design of algorithms*1 which are being used for a broad range of applications today by establishing the theory of NP-completeness. He has also developed many practically relevant computer algorithms.

It has been a long time since people first started talking about the advent of an information-oriented society. Computers have since become such an integral part of our everyday lives that we are simply unable to make do without them. Dr. Karp has developed many computer algorithms with practical relevance and these have helped to significantly reduce the time and cost of computation and manufacturing, thereby enhancing convenience and helping to create the affluent lifestyle we now enjoy. He has also established a theory on problems that require a complete search of all possibilities and belong to a complexity class that is hardest for computers to solve (NP-complete), thereby bringing about epoch-making changes to the development of large scale information systems such as software, networks, and integrated circuits.

Born in Boston in the U.S.A., Dr. Karp developed a great interest in mathematics as a child when he watched his father beautifully draw a perfect circle without using a compass. As a student of computer science at Harvard University, he was fascinated by the beauty and elegance of algorithms. In the early 1970s, Dr. Karp proposed the concept and method of interpreting (reducing) one problem into another, and showed that 21 problems related to computer science and operations research*2 are NP-complete. The establishment of the theory of NP-completeness enabled a dramatic leap in the theory of computation and algorithms which underpins computer science. The "P versus NP" problem, namely, whether the complexity class P equals the complexity class NP, is not only one of the most important unsolved questions in computer science and modern mathematics, but is also closely connected to the philosophical question, "Do finding proofs inherently require creative inspiration?"

Of the many practically relevant algorithms that Dr. Karp has developed, the Edmonds-Karp algorithm created in 1971 is one of the most famous. Used to compute the maximum flow in a given network, this algorithm is applied to increasing the efficiency of delivering electricity, gas, water, and other services fundamental to our daily lives, and relieving traffic congestion, thus helping to conserve environmental resources and reduce CO2 emissions.

Another area where Dr. Karp continues to play a leading role is the research of algorithms that allow a near optimal (but not completely optimal) solution to be found to problems that computers are unable to solve within a reasonable amount of calculation time. Furthermore, having directed his attention toward molecular biology since around 1990, Dr. Karp has been working to establish a correlation between the human gene structure and diseases, thereby also contributing to developments in medicine.

The magnitude of his fundamental contributions to the development of the theory of computational complexity is immeasurable, and holds potential for even further development beyond the framework of information science.

*1 A set of systematic computational procedures for solving a problem
*2 The study of resolving problems both scientifically and in a "logical manner"

For more details, see the Achievements.