Computational Complexity
by Christos H. Papadimitriou
149 Members (4.40)
On This Page
Description
This text offers a comprehensive and accessible treatment of the theory of algorithms and complexity - the elegant body of concepts and methods developed by computer scientists over the past 30 years for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the "structural" aspects of the P=NP question, show more parallel computation, the polynomial hierarchy, and many others. Several sophisticated and recent results are presented in a rather simple way, while many more are developed in the form of extensive notes, problems, and hints. The book is surprisingly self-contained, in that it develops all necessary mathematical prerequisites from such diverse fields as computability, logic, number theory, combinatorics and probability. show lessTags
Recommendations
Member Reviews
Members
- Recently Added By
Author Information
9+ Works 3,127 Members
Classifications
Statistics
- Members
- 149
- Popularity
- 219,644
- Rating
- (4.40)
- Languages
- English, German, Hungarian, Polish
- Media
- Paper
- ISBNs
- 4
