- Hardcover: 594 pages
- Publisher: Cambridge University Press; 1 edition (April 20, 2009)
- Language: English
- ISBN-10: 0521424267
- ISBN-13: 978-0521424264
- Product Dimensions: 8.5 x 1.4 x 10 inches
- Shipping Weight: 2.6 pounds (View shipping rates and policies)
- Average Customer Review: 31 customer reviews
- Amazon Best Sellers Rank: #201,790 in Books (See Top 100 in Books)
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
Computational Complexity: A Modern Approach 1st Edition
Use the Amazon App to scan ISBNs and compare prices.
Top 20 lists in Books
View the top 20 best sellers of all time, the most reviewed books of all time and some of our editors' favorite picks. Learn more
Frequently bought together
Customers who bought this item also bought
"This text is a major achievement that brings together all of the important developments in complexity theory. Student and researchers alike will find it to be an immensely useful resource."
Michael Sipser, MIT, author of Introduction to the Theory of Computation
"Computational complexity theory is at the core of theoretical computer science research. This book contains essentially all of the (many) exciting developments of the last two decades, with high level intuition and detailed technical proofs. It is a must for everyone interested in this field."
Avi Wigderson, Professor, Institute for Advanced Study, Princeton
"This book by two leading theoretical computer scientists provides a comprehensive,insightful and mathematically precise overview of computational complexity theory, ranging from early foundational work to emerging areas such as quantum computation and hardness of approximation. It will serve the needs of a wide audience, ranging from experienced researchers to graduate students and ambitious undergraduates seeking an introduction to the mathematical foundations of computer science. I will keep it at my side as a useful reference for my own teaching and research."
Richard M. Karp, University Professor, University of California at Berkeley
"The reviewer's impressions are that this new textbook on computational complexity is available for a very attractive price and that on Amazon it may be verified that it has received very good reviews by several leaders in this field (Karp, Sipser, Wigderson)."
Ulrich Tamm, Mathematical Reviews
This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation. It can be used as a reference, for self-study, or as a textbook. More than 300 exercises are included.
Top customer reviews
That said, I'm not crazy about this book. It is the required text for our graduate complexity theory course. I've found with some regularity that I did not really understand the assigned chapters until I attended the professor's lectures and read his slides in detail. It really seems to be geared toward presenting the most recent results in complexity theory in textbook form. I personally think it would be better suited to an advanced complexity theory course.
Contrast this with Papadimitriou's "Computational Complexity" (1993) which is a little out of date, but WOW, is it readable. Reductions, which are the bread and butter of complexity theorists get an entire chapter in Papadimitriou whereas they get a few pages in AB. Also, Papadimitriou's style is much more conversational, and he points out pitfalls and other considerations that novice mathematicians would simply miss. Oh, and Papadimitriou uses the word "trivial" sparingly, unlike AB, who sprinkle it liberally throughout their text. "Trivially"? Oh REALLY? For WHOM?!! Sorry, kind of a pet peeve of mine.
Were I a student engaging in self-study, I would obviously choose Papadimitriou despite the fact that it's a bit more expensive. It already seems like an old friend to me. I'll probably keep AB around as a reference, but it is definitely not my go-to book.
The book is full of mistakes. Virtually every proof has some small error -- a reference to a figure that is actually about something else, inadvertently swapped subscripts, like that. You can figure it out, but I, at least, spend all my time trying to understand the proof that the authors were actually trying to write down, as opposed to the garble that they actually *did* write down.
The table of contents is still great. The motivating non-technical material, by and large, is also very good, although there is some sense that complexity theory is about the P=NP question and nothing else. Even the "about this book" ends, "Onward to P versus NP!" (exclamation mark the authors').
Having bought it, I'll probably finish reading through it (I'm about 1/3 through it now). But I'm not really looking forward to it like I was before the mistakes started showing up. (Yes, I often use math and science textbooks for bedtime reading.) If I had known then what I know now, I suspect I wouldn't have purchased it at all.
I think I should make a comparison. This books is like going to Europe, spending one day in Berlin, one in Praha, two days in Paris... You see nice things... and that's all. It's never enough. You have a little bit of context, you see a few things at every place. But you soon realize that it's not enough.
Let's consider Circuit's complexity. It's covered in chapters 6, 14 and 23. You see some nice result, you begin to understand what a circuit is.. but you can not do anything with it, because three chapters are not a lot. You will need to read a book dedicated to circuit complexity if you want to really discover this subject.
Proof complexity is done in a single 10-page long chapter. Once again, I'm happy to know that this subject exists. It looks fun. But I will need a book on Proof complexity if I really want to know what this domain is.
I can't tell whether or not it is a good book for students or professor, for lectures or not, since that's not how I used this book.
The biggest down side with this book is that there are a lot of typo. And no errata online. I wrote to the authors with the list of error I found, since they state they want to hear about the book. They didn't even answer.