The Golden Ticket
As Lance carefully explains towards the end of Chapter 7, the inference from the assertion that we can only find a complete solution to an NP-complete problem by performing a brute force search of all solutions, to the assertion that P ≠ NP, forms one of the most common ways of writing a fallacious solution of the P vs NP problem. It is fallacious not because it is an invalid inference, but because it does not get rid of the need to prove something difficult: it might not be true that brute force search is the best way we can solve such problems. But it was a little disappointing that Lance did not go on to say that it is already proven that a naive brute force search is not always the best solution. Indeed, several times Lance seems to imply the equally fallacious reverse inference, from P ≠ NP to the idea that the best complete solution to an NP-complete problem must be a brute force search. For instance, this attitude is embodied in his equation of NP-completeness to "Perebor". This recent CACM article provides a welcome antidote, by describing several instances of surprising solutions to NP-complete problems that are not brute force searches and that are significantly faster than brute force (although of course not polynomial).
Despite this quibble (and smaller ones, for instance: who but a theoretician would recommend Floyd–Warshall for finding all-pairs unweighted shortest paths when one can just use repeated breadth first searches?) I think this book has an important role to play, in clearly explaining to the rest of the world just why computer scientists find the P vs NP problem so interesting and important.