Sunday, June 15, 2014

The Golden Ticket by Lance Fortnow

I finished another book today. it was The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow. I hadn't read any nonfiction in a while.

I was loaned the book by my nephew. he was awarded it for being the top grade 12 math student at Citadel High. that's a significant life accomplishment that will always stay with him. congratulations Noah, a fine young man.

The book was ok. It's about the P-NP problem in math and computer science. aka NP-Complete, see also. I'd head of it especially around the travelling salesman problem. which basically states that there's no "shortcut" trick to determine the fastest way to visit say 20 cities. the only way we know today to determine the optimal route is to list all the millions of possible ways to arrange the 20 stops, calculate the mileage on each, and from there determine which is the least.

The author Dr. Fortnow is himself a professor in computer science. He does a good job of introducing the subject in a way accessible to the layman. Fortnow is obviously comfortable in this area and an expert on the rigorous and formal mathematical side i.e. he's read and understands the Cook and Levin papers and may have done some original advanced research himself around this subject area.

There is an error in the book on page 137 in chapter 8. The author describes a two player game where P1 picks an integer. P2 without knowing the P1 number then chooses "even" or "odd". P2 wins if the guess matches the number. P1 wins if the even/odd guess does not match. The author states
If both players play randomly, each will win half the time.
This is technically true but not really accurate or optimal. it is sufficient that one player play randomly and each will win half the time. for example if P1 chooses his number at random then he is indifferent to the even/odd guessing strategy used by P2 and P1 will win half the time.  on the other hand if P2 chooses even/odd randomly then he is indifferent to the number generation scheme P1 may be using and P2 will win half the time.


Still I'd describe the book as a bit dull. he uses a running example of an imaginary place called Frenemy with 20,000 inhabitants where everyone is either a friend or enemy to everyone else. I couldn't bring myself to care or be much interested in Frenemy and the people who live there so it was kind of meh. And the clique problem. A clique is basically a group of say Facebook users who are all Facebook friends with each other. i.e. everyone is friends with everyone else in the clique. I wonder what the largest clique on Facebook is today? around 300 maybe? The first few pages around clique were pretty interesting. but I kind of wish he'd left it at some point and just moved on, even if it made the book a bit shorter. he kept coming back to clique and it was less interesting each time.

The final 2 chapters were about tangential topics quantum computers and major trends in computing today such as big data and connected devices. it wasn't readily apparent what these things had to do with P ≠ NP. they kind of felt like they had just been bolted on as additional material to fill out the book to some prescribed number of pages for publication.

well it's good to get back into nonfiction again. it's good to balance my reading. I've got some fiction on the go right now and some more nonfiction around the corner.

No comments: