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.
Rating: 
Summary: terse grad school textbook
Review: Papadimitriou is one of the great minds in computer science, which is reflected in this gem of a book. His prose is very engaging and he covers just about every topic (although be it lightly) relevant in modern complexity theory without overly diluting the proofs and results (for example, he gives a nice concise proof of Razborov's theorem on monotone circuits).
Rating: 
Summary: An excellent inroduction to computational complexity
Review: Papadimitriou is one of the great minds in computer science, which is reflected in this gem of a book. His prose is very engaging and he covers just about every topic (although be it lightly) relevant in modern complexity theory without overly diluting the proofs and results (for example, he gives a nice concise proof of Razborov's theorem on monotone circuits).
Rating: 
Summary: More understandable examples perhaps ???
Review: Things like complexity is difficult to understand.
I had a course based on this book and - althought I found it interesting - still was difficult to understand.More examples - for better understanding - would be valuable.
Rating:
Summary: Great book on Computational Complexity
Review: This book covers all from fundamentals of theory of computational complexity to recent results. The book can be easely read by a reader with larger amount of mathematical knowledge, but for non-mathematical oriented readers it maight be a problem to read this book.
Rating:
Summary: All in one roof, but presentation very poor
Review: Yes,it is generally "hard" for undergradute students even grad. students. If you are taking course "Theory of computation", I would like to recommend the Sipser's or Cohen's books for introduction's supplement. However, this book covers too many topics, therefore becomes too dense, so that you should read it carefully and slowly. For example, it introduces the "reduction" in some previous chapters but without precise defintion and therefore miss the more important part :how to do the reduction in the right way. You will find the concept of "reduction" is not very easy to catch if you refer to the Sipser's or Ullman's books. I admit that I could not go through more than 20 pages of this book in the beginning. But I was keeping on reading and surveying some "easy books". Finally, I understand most parts of this book. However, if some readers want some more advanced and recent topics. They should refer to some conference's papers hosted by ACM or IEEE.
Rating:
Summary: Be careful, but it is worth reading
Review: Yes,it is generally "hard" for undergradute students even grad. students. If you are taking course "Theory of computing", I would like to recommend Sipser's or Cohen's books for introduction's supplement. However, this book covers too many topics, therefore becomes too dense, so that you should read it carefully. I admit that I could not go through more than 20 pages of this book in the beginning. But I was keeping on reading and surveying some "easy books". Finally, I understand most parts of this book. However, if some readers want some more advanced and recent topics. They should refer to some conference's papers hosted by ACM or IEEE.
| 
