As airplane reading to and from my recent trip to Dagstuhl, I used a review copy of Lance Fortnow's new popularization of the $$\mathsf{P}$$ vs $$\mathsf{NP}$$ problem, The Golden Ticket: P, NP, and the Search for the Impossible. It's well written and explains the problem well in layman's terms, something I think has been sorely needed.

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 $$\mathsf{NP}$$-complete problem by performing a brute force search of all solutions, to the assertion that $$\mathsf{P}\ne\mathsf{NP},$$ forms one of the most common ways of writing a fallacious solution of the $$\mathsf{P}$$ vs $$\mathsf{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 $$\mathsf{P}\ne\mathsf{NP}$$ to the idea that the best complete solution to an $$\mathsf{NP}$$-complete problem must be a brute force search. For instance, this attitude is embodied in his equation of $$\mathsf{NP}$$-completeness to "Perebor". This recent CACM article provides a welcome antidote, by describing several instances of surprising solutions to $$\mathsf{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 $$\mathsf{P}$$ vs $$\mathsf{NP}$$ problem so interesting and important.