Customer Reviews

Computational Complexity: A Modern Approach

5 star:		(13)
4 star:		(4)
3 star:		(1)
2 star:		(0)
1 star:		(2)

 

 

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.

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.

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.

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 science or a related field. The book has many good and interesting exercises and is very suitable as a textbook. It can be used as a self-study textbook for researchers in other fields as well. However, the notation may not be too familiar to those who have not had any prior exposure to the topics in computational complexity. I am a theoretical Physicist and I consider myself to be fairly well versed in advanced mathematics, but I would probably want to read a book that is at a level just below this one in order to familiarize myself with the notational conventions. Otherwise, it is an extremely interesting and well-organized textbook.

I know this book is one of the best complexity book, but its Kindle Edition is the worst.
Because it is unreadable at all.

It is unable to display some important mathematical fonts (e.g. epsilon for sets, floor/ceil brackets, ...), I saw several white squares of my screen per page. Conversion (with OCR or something?) runs without accuracy, so we found two or more "glued" words (e.g. bytheway,...) per screen. I have informed each that sort of "typos" this couple of days, yes, that was a exhaustive (and un-payed) job. No, I won't do this sort of volunteer any more. So I wrote this.
The kindle edition of this book, or any other Math/Sci books likely to give seriously bad impressions not only to the originals (and authors who approved to Kindle it,) but the poor expressive capability of Kindle itself.
Please drop every suspicious kindle editions from your product list right now, and please improve accuracy of making of kindle edition.
And, if you think books are things that to be read, please revise current unreadable edition and republish it.

Why kindle edition has no "refund" or "replace kindle edition with hardcopy edition" options?

Some math and science books assume iconic status, donning the mantle of THE masterful text or learning tool. Walter Rudin's Real and Complex Analysis, John David Jackson's Classical Electrodynamics and Eugene Hecht's Optics are examples of modern classics that advanced students are usually required to work their way through. In the case of Rudin and Jackson their texts are also a rite of passage whose successful completion is so difficult that they are often used to weed-out the weaker initiates.

This new textbook is superb with an overview of the subject that has the feel of completeness as well as depth that is required of a classic text. What I found most interesting were the sections on quantum computing and cryptography, both hot topics in applied mathematics. The explanations are concise and clear with proofs and problems that are relatively difficult but not impossible to solve and are always illustrative of the text. There were a few sections of the text that I found slightly opaque and that required slow re-reading. Most math texts have sections like that so always read with a pencil in your hand. I made notes as I read and found them helpful. This is a strong textbook that increased my understanding of this important subject in computer science.

This skillfully written book is both broad in its subject matter and deep in its approach. The book begins with basic complexity theory (the classes P, NP, and their more elaborate cousins) and then sprouts in a dozen directions (quantum computing, derandomization, communication complexity, etc..) which can be read independently of each other.

I previously purchased Goldreich's "Computational Complexity", which often left me confused and frustrated. By comparison, Arora and Barak's writing is usually (excluding a few rough spots) great at helping me reach new insights.

My one complaint is that I don't think the book was sufficiently edited before publication. Phrasing is (once in a rare while) needlessly opaque and I have come across some silly typos. I wouldn't be surprised to read about a "Turning machine" on reddit, but in an advanced complexity textbook?

Anyhow, those complaints are minor and shouldn't prevent anyone from buying this book.

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. In some cases, it is difficult to discern whether a typo is just a typo or a mistake on the part of the authors. I expected a higher standard of editing. There is also a great deal of hand-waving in the proofs, which is incredibly frustrating. A textbook should explain proofs, not hint at their existence and leave the more challenging aspects of the proof to the reader.

I might suggest purchasing a supplemental text if this is the only book for your course. If you cannot, then read carefully, and always check the arithmetic and individual steps presented in proofs.

What a lovely book! I took a course in this kind of stuff a long time ago (1989, eek!), and I wish I we had used this book. However many of the topics in this book did not yet exist then. To be honest, I should say that as with most math textbooks, I have not read the whole thing and probably never will. However there is a lot I would like to learn about computational complexity, and this book will be my first reference for this subject in the future.

To give some idea of the contents: the book is divided into three parts: (1) Basic Complexity Classes, (2) Lower Bounds for Concrete Computational Models, (3) Advanced Topics. Part (1) alone is full of good stuff and worth the price of the book. To give some examples of what part (1) covers: Chapter 1 is entitled "The computational model - and why it doesn't matter". That's what I like to hear: tedious details of the computational are avoided. Chapter 2 is an introduction to NP and NP completeness. Chapter 4 discusses space complexity, ie trying to find algorithms that do not use too much memory. Chapter 7 discusses randomized computation: how much better can you perform if you can make random choices, and if you are allowed to make errors with some tiny probability? Chapter 8 introduces interactive proofs, a very fun topic. Chapter 9 gives a glimpse of cryptography. Of course cryptography is a very large topic of which not much can be covered in one chapter, but since it is obviously connected with computational complexity (you want to find codes that require astronomical computing resources to crack), it is nice to have some discussion here. Chapter 10 is a crash course in quantum computation which proceeds far enough to cover Shor's factorization algorithm. Those are just a sampling of the 23 chapters in the book.

The style of the book seems quite user friendly to me. I do have an extensive math background, so I am perfectly happy with definitions, theorems, and proofs. However the technical definitions, theorems, and proofs are supplemented by extensive informal discussions of what they mean, why they are significant, what is unknown or conjectured, etc. Anyone who has taken a few undergraduate math courses with proofs should be able to read most of the book, and even the most expert readers will appreciate the informal discussion.

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 TCS figures, for their feedback on the contents of the book yet all of these typos; should I believe that all of these people didn't see these obvious typos? The contents of the book are certainly up-to-date and the presentation is quite nice. The book assumes some prior knowledge, so good read for people with good proof/math background. Apart from that issue of typos, I'd recommend it for its simplicity and elegant way of presentation. It's a book to have in your library.