On page 3, Mary’s calculations are incorrect. The route doesn’t matter which state you start in and it is the same route whether you go in one direction or the other. So the correct number of routes is 47!/2 or the now 60 digit number 129,311,620,755,584,090,321,482,177,576,805,989,984,598,816,194,560,000,000,000.
The errors below have been corrected in the paperback edition.
In Figure 3-2 (page 34), David and Helen should not be friends.
In chapter 2, I used the fictional name Milena Pavel for the Czech woman who settled the P versus NP problem. Pavel is the male form of the name – the female form is Pavlova. Whether Milena was married and took her husbands name or was the daughter whose father’s name was Pavel, she would have taken the name Pavlova.
Don’t try to solve the large Sudoku problem on page 61, there are two G’s on the top row.
On page 55, I give credit to Richard Karp for the reduction of Satisfiability to Clique. That reduction does first appear in Karp’s paper but in that paper Karp says “the reduction to CLIQUE is implicit in Cook’s paper, and was also known to Ray Reiter.”
On page 58, the book states “It took Donald Knuth about four decades to finish volume 4.” Volume 4A of The Art of Computer Programming was published in 2011 but the rest of Volume 4 is still a work in progress.
In the map of Armenia, page 94, Shirak should have the same color as Armavir.
On page 83 the book places Novosibirsk west of Moscow when it is, in fact, east of Moscow.
The “propositions” in the parse tree on page 75 of “Golden Ticket” should be “prepositions”.
Typos
First sentence of the section on “The Hand”, page 5, “every” should be “ever”.
On Page 58, Chapter 4, the 2nd sentence in the paragraph starting with “Knuth was not entirely happy…”, it should be “English word” Knuth tried to find, not “English world”.
On Page 75, first paragraph, “difficultly” should be “difficulty”.
On page 82, since it is a sequence of digits not a number there shouldn’t be any commas (or a comma after each digit).
On page 130, “from to the day’s newspaper” should be “from today’s newspaper”.
On page 155 the book talks about the “beautiful world” in chapter 1, but the description of that world is in chapter 2.
On page 156, “buzz in that fraction of a section”, “section” should be “second”.
On page 164, Pálvölgyi Dömötör should be Dömötör Pálvölgyi.
On page 168, the Gentry paper should be dated 2009 not 1979.
——————-
Thanks to Scott Aaronson, James Blankenship, John Cherniavsky, Patrick Dymond, Nico Fortnow, Stephen Fuld, Tom Hogan, Justin Kastler, John Kristoff, Paul McJones, Dömötör Pálvölgyi, John Sigwald and Qiao Xiang.
Please email the author if you find an error in the book.