0xDE (11011110) wrote,

The Golden Ticket

As airplane reading to and from my recent trip to Dagstuhl, I used a review copy of Lance Fortnow's new popularization of the P vs 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 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.
Tags: books, complexity theory
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment