# 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)

Tags

### More like this

##### Reading Diary: Dinosaur Art: The World's Greatest Paleoart edited by Steve White
Every once in a while a review copy of a book comes over the transom and it just makes your day. Nothing else that could happen is going to put a damper on the bright sunny mood that springs from such a happy moment. One that arrived a few days ago that I can wait to read is Lance Fortnow's The…
##### Basic Complexity Classes: P and NP
Now that we've gone through a very basic introduction to computational complexity, we're ready to take a high-level glimpse at some of the more interesting things that arise from it. The one that you'll hear about most often is "P vs NP", which is what I'm going to write about today. So, what are…
##### Time for computer science to grow up?
That's the question asked by Lance Fortnow in a recent Communications of the ACM Viewpoint article (free fulltext). Fortnow's article continues a discussion about scholarly communication patterns in computer science that's been going on for a while in the "pages" of the CACM. I've blogged about it…
##### Best Science Books 2013: Amazon
It is time. The season of lists begins again! Every year for the last bunch of years I’ve been linking to and posting about all the “year’s best sciencey books” lists that I can find around the web in various media outlets. From the beginning it’s been a pretty popular service so I’m happy to…