My NP-completeness column began in 1982 in the Journal of Algorithms, initially appearing in every issue and then appearing more-and-more sporadically until it went on hiatus in 1992, with 23 editions having appeared. The column is being revived for the new ACM Transactions on Algorithms and is expected to appear semi-annually. The first of the new columns is now available. This page provides access to draft .pdf versions of all the columns. These are not exact replicas of the original columns, and the titles listed here for Columns 1-16 and 24 are descriptive summaries not present in the original text.

The .pdf files available here for Columns 1-23 were for the most part recompiled from the original troff source files using the current versions of troff, eqn, and tbl. The figures in Columns 5 and 16, which were originally produced using the no-longer-supported programs ideal and tped, were recreated using pic. The pagination in these .pdf files is typically not the same as in the definitive versions that appeared in J. Algorithms, and some of the equation formatting is subpar due to changes in the underlying typesetting software. Typos and other mistakes have not been corrected except for one in Column 22, which provides a useful summary of the contents of the first 22 columns. Exact electronic replicas of these original 23 columns (scanned .pdf files) are available for downloading from Science Direct for a fee.

The .pdf files available here for Column 24 and subsequent editions represent my drafts, and again the pagination and typesetting differs from the published version, this time because of differences in the latex macro packages used. The published versions are typically shorter and better-looking, and are available from the ACM Digital Library.

1. The Twelve Open Problems From [G&J]: Updates, J. Algorithms, 2:4 (1981), 393-405.

2. Embedding Problems, J. Algorithms, 3:1 (1982), 89-99.

3. Partitioning, Covering, and Packing Problems, J. Algorithms, 3:2 (1982), 182-195.

4. Oracles, Bin Packing, and and Ordering Problems, J. Algorithms, 3:3 (1982), 288-300.

5. Routing Problems, J. Algorithms, 3:4 (1982), 381-395.

6. Knapsacks, Linear Programs, and a Gamut of Problems, J. Algorithms, 4:1 (1983), 87-100.

7. Parallel Processing, J. Algorithms, 4:2 (1983), pp. 189-203.

8. Concurrent Processing, J. Algorithms, 4:3 (1983), pp. 286-300.

9. Fun and Games, J. Algorithms, 4:4 (1983), pp. 397-411.

10. Updates, Updates, Updates, J. Algorithms, 5:1 (1984), pp. 147-160.

11. Solving NP-Hard Problems Quickly (On Average), J. Algorithms, 5:2 (1984), pp. 284-299.

12. Randomized Algorithms and Complexity Classes, J. Algorithms, 5:3 (1984), pp. 433-447.

13. Communicating Processes, J. Algorithms, 5:4 (1984), pp. 595-609.

14. Network Design, J. Algorithms, 6:1 (1985), pp. 145-159.

15. Uniqueness, J. Algorithms, 6:2 (1985), pp. 291-305.

16. Graph Restrictions and Their Effect, J. Algorithms, 6:3 (1985), pp. 434-451.

17. Computing with One Hand Tied behind Your Back, J. Algorithms, 7:2 (1986), pp. 289-305.

18. Computing in the Math Department, Part I, J. Algorithms, 7:4 (1986), pp. 584-601.

19. The Many Faces of Polynomial Time, J. Algorithms, 8:2 (1987), pp. 285-303.

20. Announcements, Updates, and Greatest Hits, J. Algorithms, 8:3 (1987), pp. 438-448.

21. Interactive Proof Systems for Fun and Profit, J. Algorithms, 9:3 (1988), pp. 426-444.

22. The Story So Far, J. Algorithms, 11:1 (1990), pp. 144-151.

23. The Tale of the Second Prover, J. Algorithms, 13:3 (1992), pp. 502-524.

24. Open Problems Revisited, ACM Trans. Algorithms, 1:1 (2005), pp. 160-176.