The book I will be reviewing here is “The Golden Ticket: P, NP, and the Search for the Impossible,” by Lance Fortnow. If you would like to read online content by Fortnow, you check out this blog he co-authors called Computational Complexity. It explores the P=NP or P!=NP problem, and gives the reader an idea of the implications of each result.
The beginning of the book is rather slow, and is a rather long “hook” in order to get readers who may not be interested in computer science to have enough motivation to read the rest of the book. The first chapter was very interesting, and presented the multitude of cool problems that are NP such as the travelling salesman problem, cliques, and graph-coloring (a personal favorite of mine). To me, these are interesting enough to want to pursue a solution. But, of course, practical applications are most important to a lay-reader.
To catch the interest of these readers, the author then paints a fantastic possible future in which we can optimize everything: flights, weather patterns, schedules, etc.This a glorious picture of what could happen if someone creates an algorithm with solves NP problems in P time serves to provide real-world motivation to solve this problem. He admits that this is rather unlikely, but it does a great job of showing how much impact solving this problem could be.
From there, he discusses the history of the P-NP problem. I found this to be interesting, and he brought up many other important computer science results (such as the halting problem). The history and interest of the problem is explored deeply. The most interesting part of this section comes when he discusses the fact that computer scientists in the West and East both happened upon this problem, despite being separated by the Cold War.
The more interesting topics in the book follow from here. The author describes how cryptography depends on the idea that there are some problems that are too computationally difficult to solve efficiently, specifically that large numbers are hard to factorize. With P=NP, it is unlikely that we would be able to securely transmit information that has been hidden by keys.
The author then touches on different methods of proofs, and which methods have been used in attempts to solve P=NP. These were rather interesting, and difficult to digest on a first pass. I believe the author did an excellent job in his writing here, since he took a problem so difficult that it remains unsolved and explained how one may approach proving it. It also acts as a fuel for future study, as I will be attempting to read the various false proofs of the problem.
P=NP is an objectively interesting problem, and the fact the author was able to convey this to a lay audience was very astounding. I recommend this book to anyone who is interested in computation, but does not have the background necessary to read academic articles on the subject.