Customer Reviews

Computational Complexity

5 star:		(7)
4 star:		(6)
3 star:		(1)
2 star:		(0)
1 star:		(3)

 

 

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.

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

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.

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.

This is a good introductory book of computational theory for students in computer science, good juniors, seniors and first year graduates. The book is well presented, fit for self studies, and covered most contents of computability and complexity. The book is slightly old, some of the latest result are not included, e.g., a P-algorithm of solving "prime problem" was found in 2001. This book is not good for advanced researchers in theoretical computer science, it is way to shallow. Compared with Martin Davis's book, this is easier to understand, equally well presented. Be sure not to get the $8-9 version, that is not the book, although under the same title.

I am a research in theoretical algorithms.

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.

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).

We used this book for one semester when I was in the graduate school. This is one of the computer science related books that actually have enough substance to have some intellectual value.

I found this volume entertaining years after leaving graduate school and working in the industry as an engineer. The topics addressed in this book is actually quite intriguing--the best time to reduce programming complexity is before one actually programs. I believe any serious programmer should be able to estimate the complexity, both space and time, on the algorithm he is designing.

In the real world, one does not encounter nontrivial algorithms very often, and from a practical perspective, this books is not quite useful.

However, when you really get bored, this is something that could entertain your brain a little.

This book is excellent. However, you need strong training in the kind of reasoning used in math and CS theory before you can read it. The subject gets very abstract, and may be hard to follow (and that's not Papadimitriou's fault).

I would recommend it for people who have already read Sipser's book (working on the exercises), for example.

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.