It has been quite a wait between this last (24th) installment of David Johnson’s NP-completeness column and the 23rd [1], which came out in 1992. This one is the first to appear in the new journal ACM Transactions on Algorithms. Fortunately, the clarity, command, informativeness, and sense of excitement in Johnson’s writing remains truly superb, a model for anyone wishing to write about progress in theoretical computer science.

This particular column covers what progress has been made on the open problems from the famous book by Garey and Johnson [2], and from the first 23 columns. The bulk of the column focuses on the four problems that have been resolved, but whose resolutions were not already covered in the first 23 columns: composite number, even cover/minimum weight codeword, imperfect graph, and shortest vector in a lattice. The discussions are a joy to read. The column concludes with a brief discussion of “s!till open after all these years” problems. The roughly 90 citations give readers a rich set of resources to further explore the literature related to progress on the covered problems.