Most Helpful Customer Reviews
|
|
30 of 35 people found the following review helpful:
3.0 out of 5 stars
Good Information, Poorly Executed, August 22, 2000
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.
|
|
|
10 of 11 people found the following review helpful:
5.0 out of 5 stars
Excellent coverage of standard complexity topics, July 2, 1997
By A Customer
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
|
|
|
7 of 8 people found the following review helpful:
5.0 out of 5 stars
It is hard to catch some ideas, but it is worth reading, June 2, 2003
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 reading supplement. But you should keep reading this book ! IMO, this book covers so many topics, that it becomes too dense to read. It means you should read it carefully and slowly. For example, it introduces the "reduction" in some previous chapters but without precise defintion and therefore misses the more important part :how to do the reduction correctly and what is the "reseasonable" reduction ? You will find the concept of "reduction" is not very easy to catch if you refer to the Sipser's or Ullman's books. Many friends and me could not go through more than 20 pages of this book in the beginning. But we were keeping on reading and surveying some "easy books". Finally, we understood most half parts of this book. Moreover, if some readers prepare to study more advanced and recent topics, this book is the must.
|
|
|
Most Recent Customer Reviews
|
by D. S. Johnson
by Vijay V. Vazirani
by Michael Sipser
by Sanjeev Arora
