display | more...

Published in 1979, this book, or Garey and Johnson for short (after the authors), is the definitive book on NP-completeness. I personally like to call this book the little black book of NP-completeness, because it's smaller than most computer science textbooks, has a black cover, and one of the appendices (and the reason most people use the book) is a listing of NP-complete problems and where to find the proofs of their NP-completeness.

NP-Completeness

The book opens with a description of why NP-completeness is such a useful concept. It turns out that it's very difficult to prove that a given problem is guaranteed to take a computer a long time to solve. There is, however, a class of problems (the ones that are NP-complete) that are provably equivalently difficult to solve. Since nobody has yet found a good algorithm (defined here as one that runs in polynomial time), it's probably not worth working on finding a good algorithm to solve the problem exactly because so many smart people have already tried and failed.

A brief outline of the book

The first chapter goes on to define mathematically what is meant by a problem, algorithm, and the complexity of those algorithms. They discuss the fact that greater than polynomial time algorithms tend to be inefficient solutions (there's a table showing how long it will take to solve various problems, showing that exponential problems can take centuries to solve even if they're not very large problems, while polynomial problems can usually be solved in minutes or seconds.)

The second chapter brings out the heavy machinery. Here we get a proof of Cook's Theorem, that satisfiability is NP-complete. (Satisfiability is the problem of whether there exists an assignment to boolean variables that satisfies a set of boolean equations). This is an important result, because the typical way to prove that a problem is NP-complete is to show that an existing NP-complete problem is equivalent to it. All NP-completeness proofs can be traced back to the fact that satisfiability is NP-complete. In order to get this far, first they introduce the concepts of languages and Turing machines, and describe how they're a good model for computation.

Chapter three shows how to prove that a problem is NP-complete. The authors discuss six basic problems which have historically been useful to prove many other problems NP-complete. In theory, it's possible to show that any NP-complete problem is equivalent to every other problem, but some of them have much easier transformations.

In the fourth chapter, the authors introduce the concept of strong NP-completeness, and the fact that there is a hierarchy of problem complexities. We also see an example of a pseudo-polynomial time algorithm: an algorithm which can solve a problem in some variable other than the problem size. (An example of this is the partition problem: if we are trying to find a subset of objects that have a certain size, the problem is much easier if we're guaranteed that the objects are all small.) The practical upshot of this is that even though some problems are NP-complete, there are still efficient ways to solve them in some circumstances.

The fifth chapter discusses the concept of NP-hardness, as well as discussing the literature and terminology that was used to discuss NP-complete problems.

Chapter six introduces the concept of approximation algorithms. In many cases, it's difficult to solve the problem in the most efficient way, but it's easy to find a solution that's good enough (for the right definition of "good enough"...)

The last chapter of the book discusses various other problem classifications. NP-completeness deals with the time complexity of problems, where as PSPACE-completeness deals with the amount of memory it takes to solve a problem. They discuss various other classes of problems, such as #P and log-space, and end by discussing the question of P vs. NP.

The Appendix

Nearly half the book is given over to a listing of NP-complete problems, categorized according to problem domain. If you ever need to prove a problem NP-complete, look there for a problem similar to yours. (Who knows? It might even be there already...) Each problem has a description of what an instance of the problem looks like, what question the problem wants answered, a reference to the proof that showed its NP-completeness, and some comments which generally discuss related problems.

Log in or register to write something here or to contact authors.