TUGboat, Volume 36 (2015), No. 1.

Book review: Algorithmic Barriers Falling: P=NP?

Donald E. Knuth and Edgar G. Daylight, Algorithmic Barriers Falling: P=NP? Lonely Scholar, 2014, 116 pp. Paperback, US$20.00. ISBN 978-94-9138-604-6.

This is the second booklet-length interview of Donald Knuth by Edgar Daylight (done in June 2014). (For a review of the prior booklet, see http://tug.org/TUGboat/tb34-3/tb108reviews-knuth.pdf.)

Daylight is on a mission to further his “understanding of computer science by analyzing and documenting its past” (http://tug.org/interviews/daylight.html). To this end he has interviewed several pioneers of computer science and published the interviews (http://www.walden-family.com/ieee/daylight-knuth.pdf). Also to this end, Daylight and his editor Kurt De Grave have established a small publishing company for Daylight’s work.

This second interview of Knuth moves back and forth between discussion of the early days of computer science and Knuth’s current feelings about topics such as the writing of computing history and whether P=NP.

As with the first Knuth–Daylight interview booklet, this interview is interesting, easy to read, and relevant to the world of TeX.

In chapter 1, Knuth mentions how in the 1960s he decided to call the work he liked to do “analysis of algorithms” and hints that Analysis of Algorithms would have been a more appropriate name for his series of books titled The Art of Computer Programming.

In chapter 2, Knuth discusses his views on the writing of computing history (and the writing of science history more generally). He uses this discussion to include something he left out of his 2014 Stanford lecture titled “Let’s Not Dumb Down the History of Computer Science” (https://www.youtube.com/watch?v=gAXdDEQveKw), a presentation that caused a lot of debate within the sigcis.org discussion group of historians of computing. Knuth returns to this topic again in chapter 6. (Chapter 2 also touches on the development of TeX.)

Chapter 3, 4, 5, and 7 discuss various topics in the early history of computer science.

Chapter 8 is about the development of TeX and literate programming. Some parts of this are already familiar to those of us who have read about Knuth’s creation of TeX, but it also emphasizes how he moved from his original idea of trying “to express letters mathematically by measuring photographic images” (that didn’t work out well) to the idea of “capturing the intelligence of design instead of the outcome of the design.” He also explains the double meaning of the word “strokes” in the dedication of The METAFONTbook: “to Herman Zapf, whose strokes are the best”; Zapf not only draws beautiful strokes—he also stroked Knuth in the form of positive and negative critique. With regard to literate programming, I didn’t previously know that Knuth was partially influenced in the METAFONT creative effort by a report by P.-A. de Marneffe titled Holon programming: A survey.

Chapter 9 discusses the problem of whether or not P=NP and Knuth’s current opinion that P does equal NP. This chapter finishes with Knuth noting that he will write no more published papers (only books). He says his last paper was the one published in TUGboat that was the transcript of his talk on iTeX (ding) at the TeX Users Group 2010 annual conference in San Francisco (http://tug.org/TUGboat/tb31-2/tb98knut.pdf). He sees that 2010 humorous paper as the proper bookend for his first paper, also humorous, published 50 years ago in Mad Magazine.

The booklet also has a 116-element list of references and a nice index.

I recommend this interview booklet to several different classes of readers:

David Walden


$Date: 2015/02/24 17:24:33 $
TUG home page; contact webmaster; (via DuckDuckGo)