Computational complexity

Front Cover
Addison-Wesley, 1994 - Computers - 523 pages
1 Review
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, 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.

From inside the book

What people are saying - Write a review

Review: Computational Complexity

User Review  - DJ - Goodreads

recommended by Scott Aaronson as a conceptual intro to complexity Read full review

Review: Computational Complexity

User Review  - dead letter office - Goodreads

i'm not aware of too many choices for introductory graduate complexity theory. this one is not great, but it'll work. Read full review

Related books


Turing machines

19 other sections not shown

Other editions - View all

Common terms and phrases

About the author (1994)

Christos H. Papadimitriou is C. Lester Hogan Professor of Electrical Engineering and Computer Sciences at the University of California, Berkeley, where he has taught since 1996 and where he is a former Miller Fellow.

Bibliographic information