Princeton UP 2013
Date finished: 2014-07-29
A popular-level book on the computer science topic of NP-completeness. Problems in P have solutions that can be verified in polynomial time, and NP-complete problems are essentially only solvable by trying every possible solution. It isn't known whether there is any polynomial-time algorithm at all to solve NP-complete problems, much less an efficient one.
Fortnow originally wrote an article on the state of the P/NP conjecture for Communications of the ACM in 2008 and expanded it into this book. The expansion has not done the book any favours and it feels padded with a closing chapter on quantum computing, a comparison of Western and Russian work on computational complexity that's only mildly interesting, and a fictional chapter 2 of the possibilities if P=NP that was completely unconvincing. I thought the chapter on heuristics was too short: the tricks for adequately solving NP-complete problems are interesting, and Fortnow could have discussed genetic algorithms, Monte-Carlo searches, and other meaty topics. There are pieces of the book that I like, but overall it's not deep enough and focused enough, so I can't recommend it.
%T The Golden Ticket %S P, NP, and the Search for the Impossible %A Fortnow, Lance %K computing, mathematics %G ISBN 978-0-691-15649-1 %I Princeton UP %P 169pp %D 2013 %@ 2014-07-29