Customer Reviews

Computers and Intractability: A Guide to the Theory of NP-completeness (A Series of books in the mathematical sciences)

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

 

 

All those who deals with Computer Science, Mathematics and Engineering have to face the reality that certain problems seem really hard to solve. Even with the more sophisticated, and technologically advanced among the currently available computers---and among those that are to come in the next several years---, it seems highly likely that we cannot efficiently solve certain specific problems.

A first well written and systematic account on the hardness of this problems is the 1979 book on the theory of NP completeness by Michael R. Garey and David S. Johnson: Computers and Intractability, A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, San Francisco). It is amazing how, after all these years, this book remains a fundamental one to be introduced on what can be effectively and efficiently solved by computers and above all on what it seems not efficiently solvable, independently of the advances of technology. Other texts have been published after that one, as for example the recent clear and complete overview on what has been done and extensively researched since then that has been given by Christos H. Papadimitriou in his book Computational Complexity (Addison-Wesley, 1994). Nevertheless, the Garey-Johnson book---as it is often familiarly called---remains the fundamental book for a clear introduction to this central problem of what is tractable by computers.

Starting from a very clear introduction to the technical term "NP-Complete," and to how this term gained importance for the description of the algorithmic tractability of certain problems in the early 70s, the book clearly defines, both in an intuitive and then in a formal way, what it is meant by the complexity of a problem. More than that, this complexity is directly related to the effective methods for solving problems (algorithms) and thus to computers themselves. The basic of the theory of NP-Completeness is completely covered in the first 5 chapters, beginning from a low-level introduction to some of the central notions of computational complexity and finally providing detailed definitions describing proof techniques to prove the hardness of certain problems. The remaining two chapters provide an overview on two alternative directions for further study. (The both of them have been extensively investigated in the following years.) Finally, the appendix contains more than 300 main entries on NP-Complete and NP-Hard problems, and this last part of the book is continuously referenced in journal and conference papers on the subject.

The first chapter is definitely accessible also to those that doesn't know so much mathematics, or computers related stuff, and thus the book is recommendable to those that are simply curious about the things that can be solved with computers.

Every graduate CS student will probably encounter this book--it is a classic.

But long after that course in NP theory was over, the astonishment of a different aspect of the book remains.

One course assignment was the development of 15 polynomial reduction proofs (proving the computational complexity equivalence of pairs of NP problems). Part of these proofs can be simple geometric shapes, locations and connecting lines, which are defined as elements in the 2 problems. Because the elements are rigorously defined, the resulting geometric pictures model rigorous proofs of equivalence.

I was astounded at the power of such abstractions (which most programmers perhaps wouldn't even recognize as legitimate proofs). This experience underlined the fact that rigorous logical proof may take many outer forms, whether mathematical equations, formal symbolic logic proofs such as the Irving Copi notation, or simple geometric drawings.

Many veins of rich ore may be mined from this work, and only 1 of them is NP theory. But the reader must be ready to do battle with some difficult ideas, and mathematical notation which can obscure the creativity of the material covered. (For astounding creativity, examine Cooke's Theorem proving that the Satisfiability problem is NP-Complete!)

I think every computer science student should read some of this book to learn about complexity theory and the notions reducibilty and completeness. Moreover, you may come across a problem that you have to show is NP or P complete, and the examples in the book provide a good model for doing so. Papadimitriou's book on complexity is also a great place to learn more about the subject.

Yes, it's a classic. Yes, every computer scientist MUST own it. But enormous significant progress has been made in the field of NP-completeness (and computational complexity more generally) in the two decades since this book was published. An up-to-date edition -- which would probably be well over a thousand pages long -- has been badly needed for years.

I first read this book while researching heuristic techniques for reaching "good enough" solutions to the Travelling Salesman problem. "Computers and Intractability" was a breath of fresh air. It was as rigorous as any mathematical treatise, but written in a way that even a non-math major could understand. If you ever want to know why computers are so buggy, you'll know the mathematical reason for this within the first few pages of this book. By the time you reach the end, you'll never trust cryptography to absolutely, without a doubt, keep data secure for long, if at all.

I most like the fact that a good number of problems reduced to NP-Complete or NP-Hard are listed. I would like someday to see a compiled list of the reductions involved included in one text, but it's not likely that I ever will. It would be nice to see an updated version, but this describes the theory very, very nicely.

This is a must have for any serious computer scientist.

Absolutely required text. The introductory material is useful, but I must admit I've found other texts easier for that (I like Sipser's book). But the reference list of NP-complete problems, and transformations, can't be beat. I used it over and over as a student, and now just as much as a professor.

I have to say that this is a true classic. It gives a very nice treatment of what is NP-completeness in a fashion that really defends the topic well. It gives nice illustrations to show different situations and how to deal with it. But after the first couple of chapters it does get a little out there with the proofs it does. It is still approachable, but it assumes that the reader is already familiar with the basics of combinatorial complexity, especially in reductions. I would only recommend this book to readers who has gone through such books as Introduction to Algorithms by Cormen et al. or Combinatorial Complexity by Papadimitriou and Steiglitz. Those two books are more for beginners and this book should be one to help anyone interested in NP-complete problems to get more practice and depth understanding. Overall a great book for anyone interested in the topic. The grand challenge is to reduce everything to at least something within the 150 problems listed on your own.

This is a rare example of a textbook where the authors actually go to the trouble of considering the fact that the intended reader is a non-expert. Published in 1979 and still the best.

The book is excellent in explaining NP-completeness problem. Take it as a reference if you would like to do research in this field.