Reading Diary: The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow

Someone shoot me if I ever use the term NP-complete in a sentence. Or at least if I ever use the term in a conversation with "civilians."

Such is the dilemma of reading and reviewing a wonderful book like Lance Fortnow's The Golden Ticket: P, NP, and the Search for the Impossible. I'll be tempted to start throwing around terms that Fortnow has explained so well and so clearly. A temptation I should resist. Instead I should recommend this book.

Anyways, what's the book about? As the title indicates, the purpose is to explain to a popular audience the computer science concept of P vs. NP, in other words is P = NP or is P != NP.

Yeah, not helpful put that way.

A rather nice explanation from the jacket blurb:

The P-NP problem is the most important open problem in computer science, if not all of mathematics. Simply stated, it asks whether every problem whose solution can be quickly checked by computer can also be quickly solved by computer.

And from page ix:

P refers to the problems we can solve quickly using computers. NP refers to the problems to which we would like to find the best solutions. If P = NP, then we can easily find the solution to every problem we would like to solve....If P != NP, by contrast, then there are some problems we cannot hope to solve quickly.

And Fortnow takes it from there, sketching the history of the P vs NP pursuit since it was first formulated in the 1970s up until the present. He also sketches out a bit of a utopian vision of how society would change, how it would become what he calls a beautiful world, if P = NP. If we can know for sure that all problems ultimately have fast solutions, then it's only a matter of time before we discover them. And solve all our problems.

However, Fortnow doesn't think that P = NP. He thinks that there is no possible ultimate beautiful world, but that we will have to strive to find "good enough" solutions to those hard problems. And yes, he does talk about what those hard problems are in theoretical computer science and how they affect our everyday lives. Cryptography is perhaps the most well-known application area for those hard problems. Fortnow doesn't think we are anywhere near to solving P vs NP, that we may even be hundreds of years away. Or that we may never solve it.

Overall a fine book. Comparable in level to a physics book by say, Sean Carroll or Lee Smolin. In other words, you will have to challenge your mind a little to grasp every example and problem description. I would recommend the book for any academic library collection collects popular science. In particular, since there seems to be fewer popular computer science books than other fields, Fortnow's book fills a gap. I would normally not suggest this type of book for smallish public libraries, but again it does fill that gap. As for school libraries, mathematically gifted students at the high school level would find a lot to love about this book.

At the end of the day, it's also wonderful to see a computer science book that thanks the library for its print and digital collections in the Acknowledgements. Thanks for the hat tip, Lance, we appreciate it. And thanks for the nice bibliography of sources worth checking out.

Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton: Princeton University Press, 2013. 176pp. ISBN-13: 978-0691156491

(Review copy provided by publisher)