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.

Abstract of the Commemorative lecture
The Power and Limits of Algorithms

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.