This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set.
Computational Complexity
and over one million other books are available for Amazon Kindle. Learn more
 |
| |||||||||||||||
Save up to 70% when you rent your textbooks on Amazon. Keep your textbook rentals for a semester and rental return shipping is free. |
Book Description
Frequently Bought Together
Editorial Reviews
Review
"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
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
Book Description
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.
Product Details
Would you like to update product info or give feedback on images? |
More About the Author
Discover books, learn about writers, read author blogs, and more.
Customer Reviews
Most Helpful Customer Reviews
19 of 19 people found the following review helpful
By NULL VOID
Format:Hardcover
I own two copies of this book: a hardcopy I keep at home, and the PDF version on my Nook (which I bought directly from the publisher). I'm happy that there is an eBook version given that I often run or bike to school and don't have to lug this thing around with me.
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.
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.
40 of 45 people found the following review helpful
Format:Hardcover|Amazon Vine™ Review
(What's this?)
I almost didn't order this book. I had visions of opening the box and pulling out some incomprehensible tome with one coma-inducing proof after another. I have a BS in math, but that was an embarrassingly long time ago, so I wasn't sure I was up for a real test of my sanity. What a relief it was to see that this book is relatively approachable.
OK, wait -- quick sanity check. This *is* a textbook about the mathematical analysis of computation; hopefully you wouldn't even be reading this review if you couldn't wade through a jungle of mathematical proofs, if you didn't know some discrete math, graph theory, etc., or if you didn't have some programming experience. There are formal notations everywhere. The subject matter of this book sets a pretty high bar, regardless of how the book is written.
So, back to how the book is written. Very well! Yes, there are proofs and lemmas everywhere, but the authors do several things to focus on getting the point across without being tiresome. First, they are great about motivating what they are talking about. Why is this issue important? Why are we going to approach the problem this way? Second, they are generous with well thought out diagrams that depict what is being described in words. A few good diagrams go a long way with me, personally. Third, in some cases they just give "hand-wavy proofs." By not getting hung up the formality of the proofs, they can choose interesting statements to prove and get the idea across in a paragraph. May I just say "Hallelujah!" -- I wish more books took this approach, concentrating more on understanding than on formality. Fourth, they sometimes take two runs at a proof, once just talking their way through it, saying what is going to happen, and then going back over it a second time formally. Fifth, they have quite interesting "chapter notes" that give interesting history about how a topic developed over the years and how it has been important in the "real world." The book is also very well typeset -- easy on the eye.
I was delighted to see a section on cryptography followed by a section on quantum computing, which has huge implications for cryptography precisely because of what it means for computational complexity (of integer factorization, in particular). The section "Shor's ideas in nutshell" is a perfect example of how the authors took something that could have been quite tedious and talked the (prepared) reader through it in a way that is not only comprehensible but interesting.
This is not to say that the book is not rigorous. But rigorous doesn't have to be tedious.
I will try to update this later as I read further, but so far, I'm quite impressed. This book assumes you have some serious background, but then treats you kindly.
Oh, and the price -- it's less than half what I would have expected a book like this to cost. I thought I was reviewing the wrong book for a minute! :^) Kudos to Cambridge University Press for keeping prices down.
OK, wait -- quick sanity check. This *is* a textbook about the mathematical analysis of computation; hopefully you wouldn't even be reading this review if you couldn't wade through a jungle of mathematical proofs, if you didn't know some discrete math, graph theory, etc., or if you didn't have some programming experience. There are formal notations everywhere. The subject matter of this book sets a pretty high bar, regardless of how the book is written.
So, back to how the book is written. Very well! Yes, there are proofs and lemmas everywhere, but the authors do several things to focus on getting the point across without being tiresome. First, they are great about motivating what they are talking about. Why is this issue important? Why are we going to approach the problem this way? Second, they are generous with well thought out diagrams that depict what is being described in words. A few good diagrams go a long way with me, personally. Third, in some cases they just give "hand-wavy proofs." By not getting hung up the formality of the proofs, they can choose interesting statements to prove and get the idea across in a paragraph. May I just say "Hallelujah!" -- I wish more books took this approach, concentrating more on understanding than on formality. Fourth, they sometimes take two runs at a proof, once just talking their way through it, saying what is going to happen, and then going back over it a second time formally. Fifth, they have quite interesting "chapter notes" that give interesting history about how a topic developed over the years and how it has been important in the "real world." The book is also very well typeset -- easy on the eye.
I was delighted to see a section on cryptography followed by a section on quantum computing, which has huge implications for cryptography precisely because of what it means for computational complexity (of integer factorization, in particular). The section "Shor's ideas in nutshell" is a perfect example of how the authors took something that could have been quite tedious and talked the (prepared) reader through it in a way that is not only comprehensible but interesting.
This is not to say that the book is not rigorous. But rigorous doesn't have to be tedious.
I will try to update this later as I read further, but so far, I'm quite impressed. This book assumes you have some serious background, but then treats you kindly.
Oh, and the price -- it's less than half what I would have expected a book like this to cost. I thought I was reviewing the wrong book for a minute! :^) Kudos to Cambridge University Press for keeping prices down.
23 of 27 people found the following review helpful
Format:Hardcover|Amazon Vine™ Review
(What's this?)
Amazon Vine Review
This is a 500 page textbook for a graduate course written by two Princeton professors who are experts in the field. As a non-expert I am not qualified to review it on technical grounds, but I was intrigued by the authors' claim to require of readers only minimal computational and mathematical background. In their introduction they state:
"This book aims to describe such recent achievements of complexity theory in the context of more classical results. It is intended to serve both as a textbook and as a reference for self-study. This means it must simultaneously cater to many audiences, and it is carefully designed with that goal in mind. We assume essentially no computational background and very minimal mathematical background, which we review in Appendix A."
I thought it would be an interesting experiment to see just how much I could learn about the topic just from the book itself. I did succeed in getting quite a bit more than I expected from dipping into it at various points, but in the end I was reminded of P.F. Strawson's remark that "There is no shallow end to the philosophical pool." The computational complexity pool is similarly configured.
The fundamental background for this field was set up in the 1930's by logicians such as Alan Turing and Alonzo Church whose work gave the answer to what constitutes a computable function. Turing described a simple type of abstract machine and showed that such a machine could compute any computable function.
With the question of what is theoretically computable decisively settled, the question turns to what is computable efficiently--that is, within an amount of time determined by the size of the input raised to some power.
The central and unsolved problem of computational complexity is whether the class P of decision problems which can be efficiently solved (that is, computed by a Turing machine in polynomial time) is the same as the class NP of problems whose solution can be efficiently verified. Verification is generally a much simpler task than finding a solution, which might require long searches. The authors do an excellent job of explaining the philosophical significance of this problem as well as its practical importance. As they put it, if P = NP, "then the world would be mostly a computational Utopia."
Even for the non-technical reader there are many interesting and delightful things in this book and my (non-technical) guess would be that with it is going to become the standard reference and textbook in the field. Whether the general reader will find it penetrable is a much different question, and I suspect she won't. The reason is not the fault of the book--it is extremely well-written--but of human psychology: new ideas take a while to become familiar enough that you can work with them.
The authors, who have done such a marvelous job with this book aimed at the professional audience in computational complexity, could do us all a great service by writing another book aimed at a general audience. Clearly they have the knowledge and the writing skills to make this field more broadly accessible and the topics involved are fascinating and important.
This is a 500 page textbook for a graduate course written by two Princeton professors who are experts in the field. As a non-expert I am not qualified to review it on technical grounds, but I was intrigued by the authors' claim to require of readers only minimal computational and mathematical background. In their introduction they state:
"This book aims to describe such recent achievements of complexity theory in the context of more classical results. It is intended to serve both as a textbook and as a reference for self-study. This means it must simultaneously cater to many audiences, and it is carefully designed with that goal in mind. We assume essentially no computational background and very minimal mathematical background, which we review in Appendix A."
I thought it would be an interesting experiment to see just how much I could learn about the topic just from the book itself. I did succeed in getting quite a bit more than I expected from dipping into it at various points, but in the end I was reminded of P.F. Strawson's remark that "There is no shallow end to the philosophical pool." The computational complexity pool is similarly configured.
The fundamental background for this field was set up in the 1930's by logicians such as Alan Turing and Alonzo Church whose work gave the answer to what constitutes a computable function. Turing described a simple type of abstract machine and showed that such a machine could compute any computable function.
With the question of what is theoretically computable decisively settled, the question turns to what is computable efficiently--that is, within an amount of time determined by the size of the input raised to some power.
The central and unsolved problem of computational complexity is whether the class P of decision problems which can be efficiently solved (that is, computed by a Turing machine in polynomial time) is the same as the class NP of problems whose solution can be efficiently verified. Verification is generally a much simpler task than finding a solution, which might require long searches. The authors do an excellent job of explaining the philosophical significance of this problem as well as its practical importance. As they put it, if P = NP, "then the world would be mostly a computational Utopia."
Even for the non-technical reader there are many interesting and delightful things in this book and my (non-technical) guess would be that with it is going to become the standard reference and textbook in the field. Whether the general reader will find it penetrable is a much different question, and I suspect she won't. The reason is not the fault of the book--it is extremely well-written--but of human psychology: new ideas take a while to become familiar enough that you can work with them.
The authors, who have done such a marvelous job with this book aimed at the professional audience in computational complexity, could do us all a great service by writing another book aimed at a general audience. Clearly they have the knowledge and the writing skills to make this field more broadly accessible and the topics involved are fascinating and important.
Most Recent Customer Reviews
5.0 out of 5 stars
Extraordinary pertect
This book is a bible in computational complexity. An Up to date. I recommend it. And I have some time teaching this topic
Published 3 months ago by Oscar Meza
5.0 out of 5 stars
The best
about introduction to complexity, the best without a doubt. An excellent book for consulting and for courses. Very complete. It's principally theory. Read more
Published 15 months ago by David Salas Videla
1.0 out of 5 stars
Frustrating: Kindle Edition Needs Major Revisions
I know this book is one of the best complexity book, but its Kindle Edition is the worst.
Because it is unreadable at all. Read more
Because it is unreadable at all. Read more
Published 19 months ago by write(eval(read(.))
5.0 out of 5 stars
Computational Complexity:
This book is excellent and covers the most important and fundamental concepts in the theory. The exercises are pretty good and make you think. Read more
Published on April 17, 2011 by Chaman Singh Verma
4.0 out of 5 stars
Read this book carefully!
For the most part, Arora and Barak provide a relatively solid introduction to complexity; however, as a previous reviewer noted, the number of typos is astounding. Read more
Published on November 30, 2010 by Allison T. Brown
1.0 out of 5 stars
Reding the kindle version sample
I downloaded a sample of this for my kindle. I was really disapointed to find that the math did not look good at all on the kindle's screen. Read more
Published on November 7, 2010
4.0 out of 5 stars
Good, with many typos
I just was bothered by the typos in this book. They are countless. In the preface, Barak and Arora thank a long list of people, among whom some are very well known and respected... Read more
Published on April 3, 2010 by Voltaire
5.0 out of 5 stars
A comprehensive modern textbook
This is a very comprehensive and detailed book on computational complexity. Its target audience are the advanced undergraduates or the first-year graduate students in computational... Read more
Published on February 8, 2010 by Dr. Bojan Tunguz
5.0 out of 5 stars
Well written and understandable
It has been several years since I studied anything related to this subject and was curious and hesitant about getting this book since I wasn't sure I wanted to get into a lot of... Read more
Published on September 27, 2009 by L. Romero
5.0 out of 5 stars
On The Same Par As Cormen's Algorithms
This book requires extensive mathematical background but is very thorough for those interested in complexity
"Turing machines, basic time and space complexity classes,... Read more
"Turing machines, basic time and space complexity classes,... Read more
Published on September 17, 2009 by John Grove
