The NP-completeness column: An ongoing guide (Number 20: Announcements, Updates, and Greatest Hits).
01 January 1987
This memo contains the twentieth edition of a quarterly column that appears in the Journal of Algorithms. It discusses the recent flurry of claimed resolutions to the P versus NP question, provides updates on the topics of recent columns, and concludes with a first for the NP-completeness column: an actual NP-completeness proof (from one of the two most requested unpublished references cited in [G&J]).