Monday 19 October 2015

A Brief History of NP-Completeness, 1954–2012

David S. Johnson has written a paper called A Brief History of NP-Completeness, 1954–2012. The year 2012 was the 100th anniversary of the birth of Alan Turing and the 40th anniversary of Richard Karp's important paper detailing 23 NP-complete problems. If the subject of NP-completeness and P$=$NP interests you, then you might enjoy reading this paper about the history of computational complexity theory.