Richard M. Karp
Abstract
The 1985 Turing Award winner presents his perspective on the development of the field that has come to be called theoretical computer science.
Index Terms
- Combinatorics, complexity, and randomness
Recommendations
Rethinking Randomness: An interview with Jeff Buzen, Part II
In Part 1, Jeff Buzen discussed the basic principles of his new approach to randomness, which is the topic of his book Rethinking Randomness. He continues here with a more detailed discussion of models that have been used successfully to predict the ...
Rethinking Randomness: An interview with Jeff Buzen, Part I
For more than 40 years, Jeffrey Buzen has been a leader in performance prediction of computer systems and networks. His first major contribution was an algorithm, known now as Buzen's Algorithm, that calculated the throughput and response time of any ...
Reviews
S. Srinivasan
This is the ACM 1985 Turing Award Lecture paper. In this expository paper, the author traces the history of the work in the area of computational complexity. The chart on the development of combinatorial optimization and computational complexity very succinctly presents all the major developments from 1900 to the current time. The author has outlined the work of various people, such as M. Held, L. Ford, and S. Cook. By its very nature, the paper does not get into any technical details. However, the account of work done in the area of the Traveling Salesman problem and other NP-complete problems is very enlightening. The account of the work on linear programming problems and application of probability techniques to simplex algorithms is fairly detailed. This paper has no bibliography. Nonetheless, the paper should appeal to a very wide audience.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments