Fortnow, Lance

Princeton UP
2013

ISBN 978-0-691-15649-1

169pp

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

Permalink: http://books.amk.ca/2014/07/Golden_Ticket.html