The Golden Ticket: P, NP, and the Search for the Impossible

Fortnow, Lance
Princeton UP 2013
ISBN 978-0-691-15649-1
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.

Tagged: computing, mathematics


%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

Contact me