Computers and Intractability

Computers and intractability : a guide to the theory of NP-completeness by Michael R. Garey and David S. Johnson is a standard textbook for those interested in the theory of NP completeness.

This work is in three parts. The first introduces NP completeness and describes how to go about proving that a problem is NP complete. The second part looks at more advanced topics, such as the structure of the class of NP problems - you might think of all NP complete problems as being more or less the same, but the authors show that there is more it than that. They also describe tractable ways of obtaining approximate solutions to NP complete problems.

It's the third part which will be the most important for most people though. This consists of a list of a large number of NP complete problems including references to the proof of their NP completeness. So whether you are you are a student of computational complexity, you are thinking of attacking the million dollar P=NP question, or you just have to write a program for a problem which you think might be NP complete, you will find that this book is a useful addition to your library.