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.