. I first heard about this book while watching Steven Skiena's online video lectures (which I blogged about recently) three or four years ago, where he recommends it as the best book on the topic (and actually uses it in class). I've since read it several times and used it as reference many more, and before going into the details, I'll just say I think it's awesome.And now for the details :). This is not your standard "read before sleep" book. It's more like a math book (and math books are read with pen and paper in hand :). When I first tried reading it (that was when I had just a basic grasp on the topic), I found it pretty hard going, and had to restart a few times. This is not to say it's not well written; on the contrary, the writing is great. It just took me a while to get into the right mindset for it. If you're a fan of formalisms and Turing machines, you'll have no problems whatsoever. If you're not, but still want to understand this stuff, you'll have to make more of an effort, but I think it's well worth it. The book doesn't force formalisms down your throat for no reason, but develops the theory from the formal to the informal and more intuitive (but still correct) in a very elegant way.
The book is logically divided into three parts. In the first part, you'll learn why complexity matters and some basic terminology regarding Turing machines, languages, encoding schemes, decision problems and "real problems" (and how they all relate to each other) and the all important polynomial transformation between problems. Then you'll read about what it means for a problem to be in P and NP. After this introduction, the authors present Cook's theorem that is basically the origin of the whole story, in which the famous satisfiability problem is defined and proved to be NP-complete. What follows are proofs (via polynomial transformation) that "6 basic" NP-complete problems are indeed NP-complete. These are 3-satisfiability, 3-dimension matching, vertex cover, clique, hamiltonian circuit and partition. These transformations are a bit more involved then most (since you don't have many problems to choose from when you start building up the NP-complete set), as is the proof of Cook's theorem, but I find them mathematically beautiful (and in general, constructing NP-completeness proofs is a nice mind "game", not to mention useful in many cases :). However, on your first reading, you'll probably want to skim these and just get the intuition behind them and understand "the big picture".
After that, the authors take a step back and try to define three general techniques for constructing NP-completeness proofs (restriction, local replacement and component design) and show a few examples of each. You are then presented with fourteen exercise problems on which to try the techniques out. This ends the first part of the book (about 65 pages).
The second part of the book starts with exploring how the NP-completeness of a problem changes when you constrain it or change it. Then it explains what it means for a problem to be NP-complete in the strong sense and what are Turing reducibility and NP-hardness. The next chapter gives some basic information about dealing with NP-complete problems through approximation algorithms, but what I think is far more interesting (in the context of this book), they show how using the theory of NP-completeness you can prove that some problems can't even be approximated well (for certain definitions of "a good approximation" which I won't go into here) in polynomial time (unless P = NP). The second part ends with expanding the complexity hierarchy with some more advanced concepts like co-NP, gama-reductions and gama-completeness, #P-completeness, PSPACE, DLOGSPACE, EXPTIME etc. (these are all covered with examples and provide solid intuition about what these things are on the first reading, but need to be studied a bit more carefully for full understanding).
Finally, the third part of the book is a catalog of about 300 NP-complete problems (sorted into several categories). This is a great reference! If you have an NP-complete problem on your hands, chances are it has a name and it's on this list :) Given the age of this book, I'd imagine the current list of known NP-complete problems is somewhat bigger, but this one is comprehensive enough that you can probably at least find a problem that is close enough to your problem that you'll be able to construct a proof yourself.
So to summarize, this is an awesome book. NP-complete problems pop up just about everywhere, and it's important to be able to recognize them (and not waste too much time trying to solve them to optimality quickly). My advice for a reading algorithm: read the first part, skimming over the proofs for intuition, then reread it a month later going through the proofs with pen and paper. Then read the second part (it's not as important so you can skim it or read it for full comprehension, depending on how much you want to get out of it) and skim the catalog to get a feel for which problems are there (so you can use it as a reference). You'll recognize quite a few of them, probably some you've met at work :). Also, even if you're not in Computer Science, you might like this book from an epistemological perspective ;)
Posts
0 comments:
Post a Comment