Rating: 
Summary: Upon Leaving The Realm Of Sense, For Points Distant
Review: *Computational Complexity* is a great introduction to contemporary formal logic, which is more heavily mathematical than even the great mathematical logicians of the past were. It's a great introduction, even though they put a good-lookin' chick on the *back* cover (what's that about?), because Papadimitriou does not suffer from what Quine called *mathematosis* -- he is not assimilating the material of logic (anything and everything symbolic) to the rigorized abstractions of mathematics. And as such, this book defines what I think *computer science* should be today by choosing the "greater of two evils". If you think that computer science began with Turing like most people, CS is about building machines that do what thinking beings do (problems of detail); but if you think that computer science began with Church's undecidability theorem, CS would be about figuring out why thinking beings fall down on the reasoning job (troubles with principle). I prefer the second definition; and although I'm a little old-fashioned in my tastes (prove it by me), this book demonstrates such an attitude can be forward-looking. Although Church is not venerated throughout the book, a task handled by Papadimitriou in his earlier CS introduction with Lewis, unlike Hopcroft and Ullman the spirit of Church is very much present in Papadimitriou's teasing-apart of complexity problems from applied CS. Yes, it's never about the physical machine, and Ryle can go away instead of work like this -- which in my opinion could form the basis of a "computational psychology" concerned with the will to truth rather than the will to power.
Rating:
Summary: Understanding The Mad Chronic Sacks Of Phat Buds
Review: *Computational Complexity* is a great introduction to contemporary formal logic, which is more heavily mathematical than even the great mathematical logicians of the past were. It's a great introduction, even though they put a good-lookin' chick on the *back* cover (what's that about?), because Papadimitriou does not suffer from what Quine called *mathematosis* -- he is not assimilating the material of logic (anything and everything symbolic) to the rigorized abstractions of mathematics. And as such, this book defines what I think *computer science* should be today by choosing the "greater of two evils". If you think that computer science began with Turing like most people, CS is about building machines that do what thinking beings do (problems of detail); but if you think that computer science began with Church's undecidability theorem, CS would be about figuring out why thinking beings fall down on the reasoning job (troubles with principle). I prefer the second definition; and although I'm a little old-fashioned in my tastes (prove it by me), this book demonstrates such an attitude can be forward-looking. Although Church is not venerated throughout the book, a task handled by Papadimitriou in his earlier CS introduction with Lewis, unlike Hopcroft and Ullman the spirit of Church is very much present in Papadimitriou's teasing-apart of complexity problems from applied CS. Yes, it's never about the physical machine, and Ryle can go away instead of work like this -- which in my opinion could form the basis of a "computational psychology" concerned with the will to truth rather than the will to power.
Rating:
Summary: Good overall.
Review: A well-written book that teaches you how to think about complexity theory instead of just a flat summary of results. Something like Lewis and Papadimitriou's _Elements of the Theory of Computation_ would be more than enough preparation for this (note that the style of these books is quite different- this one is more informal and descriptive). Covers all the material you need in a first text. Has a good little introduction to mathematical logic in it, including a nice succinct version of Godels Incompleteness Theorem. Lots of interesting exercises.
Rating: 
Summary: For the Student
Review: As an undergraduate computer science student studying theory, I found this book facinating and helpful. It clearly explained the primary concepts of complexity. The theorems are useful and the proofs are fairly straightforward. All in all, an interesting read. He spends a little bit too much time on logic, and his proof of Rice's theorem is a bit odd, but all in all this is a great book.
Rating:
Summary: For the Student
Review: As an undergraduate computer science student studying theory, I found this book facinating and helpful. It clearly explained the primary concepts of complexity. The theorems are useful and the proofs are fairly straightforward. All in all, an interesting read. He spends a little bit too much time on logic, and his proof of Rice's theorem is a bit odd, but all in all this is a great book.
Rating:
Summary: Excellent coverage of standard complexity topics
Review: By far, the best book on complexity theory that I have ever read. I disagree with another reviewer's assessment of a lack of feasibility issues; that's not the focus of this book, nor should it be the focus of any book on complexity theory. 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
Rating: 
Summary: All in one roof, but presentation very poor
Review: I agree with the review by Arthur Fischer. Papadimitriou might
be an excellent researcher, but his communication skills are
hopeless and horrible. The typos make learning even harder. Perhaps someone like Michael Sipser should take up the task of
rewriting this book.
Rating:
Summary: terse grad school textbook
Review: I bought this book after reading a review describing it as a good book on algorithm complexity. What I didn't know was that the book states in the preface: "This book in an introduction to the theory of computational complexity at a level appropriate for a beginning graduate or advanced undergraduate course." In other words, it is best used as part of a course where you'll have an instructor give a less terse version of what this guy is trying to say. I am a college educated software developer, so I've been exposed to logic statements, but I was expecting to find something of use for software development, rather then a formal college text book (think lots of Theorem / Lemma / Proof sections followed by problem sets, etc). Clearly I am not the target audience for this book.
Rating:
Summary: Challenging
Review: I found this book hard to follow. However, I suspect I did not have the strong background in complexity theory required by it. This probably should not be the first book you read on this subject. It is a dense book and will probably reward intense study. Also I think it is a good reference as it discusses most of the important complexity classes out there. The only problem is that I think it is slightly outdated by now, being published in 1994 and hence does not contain much discussion of the latest results especially on inapproximability, the PCP theorem and so on. However, this is THE standard text on complexity theory and many people swear by it, which is why I still give it 5 stars.
Rating: 
Summary: Good Information, Poorly Executed
Review: I used this book for a reading course in Complexity Theory. In going through the text, I found that though most topics were introduced in a fairly thorough manner, with enough axamples to make them understabdable, sometimes Papadimitriou would make some fairly simple mistakes. Of course, hese mistakes may be seen as typos in many places, but the sheer volume of them is difficult to attribute to typos alone. The readability of a proof, or a solution to an example is greatly reduced with the presence of inconsistent notations, and plain mathematical garbage. 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.
| 
