2008Advanced TechnologyInformation Science
Richard Manning Karp photo

Richard Manning Karp

  • U.S.A. / January 3, 1935
  • Computer Scientist
  • University Professor, University of California, Berkeley ; Senior Research Scientist, International Computer Science Institute

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.

Profile

Brief Biography

1935
Born in Boston, Massachusetts, U.S.A.
1959
Ph.D. (Applied Mathematics), Harvard University
1959
Research Staff Member, IBM Thomas J. Watson Research Center
1968
Professor, University of California, Berkeley
1988
Research Scientist, International Computer Science Institute
1995
Professor, University of Washington
1999
University Professor, University of California, Berkeley
Senior Research Scientist, International Computer Science Institute

Selected Awards and Honors

1979
Delbert Ray Fulkerson Prize in Discrete Mathematics, Mathematical Programming Society and American Mathematical Society
1985
A.M.Turing Award, Association for Computing Machinery
1986
Distinguished Teaching Award, University of California, Berkeley
1996
National Medal of Science
1998
Harvey Prize, The Technion-Israel Institute of Technology
2004
Benjamin Franklin Medal, The Franklin Institute
Member:
National Academy of Sciences, National Academy of Engineering, American Academy of Arts and Sciences, American Association for the Advancement of Science, American Philosophical Society

Selected Publications

1971

The traveling-salesman problem and minimum spanning trees: Part II (Held, M. and Karp, R.). Mathematical Programming 1: 6-25, 1971.

1972

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.

1972

Theoretical improvements in algorithmic efficiency for network flow problems (Edmonds, J. and Karp, R.). Journal of the ACM 19: 248-264, 1972.

1979

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.

1985

A fast parallel algorithm for the maximal independent set problem (with Wigderson, A.). Journal of the ACM 32: 762-773, 1985.

2003

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.

Citation

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.

Lecture

Abstract of the 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.

[Read More]
Full Text(PDF)
Workshop

Workshop

Computational Approach to Science: Our Dream and Your Dream

date
13:00 - 17:30, November 12, 2008 (Wed.)
palce
Kyoto International Conference Center
Coordinator
Yoshiyasu Inagaki (Chairman, Kyoto Prize Committee; Executive Trustee, Vice-President, Toyohashi University of Technology)
Coordinator/Moderator
Osamu Watanabe (Professor, Graduate School of Information Science and Engineering, Tokyo Institute of Technology)
Organized by Inamori Foundation

Program

13:00
Opening Address Yasuyoshi Inagaki
Introduction of Laureate Osamu Watanabe
13:15
Laureate Lecture Richard Manning Karp (the Laureate in Advanced Technology)
“Understanding Science through the Lens of Computation”
14:15
Intermission
14:30
Lecture Satoru Miyano (Professor, Institute of Medical Science, The University of Tokyo)
“Biology as Computational Science”
15:05
Lecture Mitsunori Ogihara (Professor, Department of Computer Science, University of Miami)
“Algorithmic Analysis of Network Traffic”
15:40
Lecture Osamu Watanabe
“Algorithmic Understanding of Some Stochastic Methods”
16:15
Intermission
16:30
Panel Discussion “Computational Approach to Science: Our Dream and Your Dream”
Moderator Osamu Watanabe
Panelists Richard Manning Karp
Satoru Miyano
Mitsunori Ogihara
17:30
Closing
PAGETOP