![]() |
| |||||||||||||||
|
Rent Your Textbooks
Save up to 70% when you rent your textbooks on Amazon. Keep your textbook rentals for a semester and rental return shipping is free. |
This new 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 field as computability, logic, number theory, combinatorics, and probability.
Features
- First unified introduction to computational complexity.
- Integrates computation, applications, and logic throughout.
- Provides an accessible introduction to logic, including Boolean logic, first-order logic, and second-order logic.
- Includes extensive exercises including historical notes, references, and challeging problems.
Product Details
Would you like to update product info or give feedback on images? |
The set of references and notes listed at the conclusion of most chapters was excellent, but the reader is to beware that some of the references listed are wrong (Cook's Theorem is from the 3rd ACM Symp. on Found. of Comp.Sci., not the 3rd IEEE Symp. on Found. of Comp. Sci., for instance).
These problems make it difficult for the comitted learner to get all the information he/she wants, and greatly detracted from my enjoyment of the text.
Unfortunately, I am unable to direct people to a more consistent text in Complexity Theory suitable for the senior undergrad through graduate levels.
Papadimitriou's proofs are complete, concise, and understandable, which is more than I can say for most books on the subject. If you are interested in an in-depth coverage of a wide range of topics relating to complexity theory, this book is an excellent starting point. Highly recommended