David S. Johnson
Last Updated: 8 Auguest 2005
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
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.
- The Twelve Open Problems From [G&J]: Updates,
- Embedding Problems,
- Partitioning, Covering, and Packing Problems,
- Oracles, Bin Packing, and and Ordering Problems,
- Routing Problems,
- Knapsacks, Linear Programs, and a Gamut of Problems,
- Parallel Processing,
- Concurrent Processing,
- Fun and Games,
- Updates, Updates, Updates,
- Solving NP-Hard Problems Quickly (On Average),
- Randomized Algorithms and Complexity Classes,
- Communicating Processes,
- Network Design,
- Graph Restrictions and Their Effect,
- Computing with One Hand Tied behind Your Back,
- Computing in the Math Department, Part I,
- The Many Faces of Polynomial Time,
- Announcements, Updates, and Greatest Hits,
- Interactive Proof Systems for Fun and Profit,
- The Story So Far,
- The Tale of the Second Prover,
- Open Problems Revisited,
ACM Trans. Algorithms,