DOCUMENTA MATHEMATICA, Vol. Extra Volume: Optimization Stories (2012), 359-376

David S. Johnson

A Brief History of NP-Completeness, 1954--2012

2010 Mathematics Subject Classification: 68-03, 68Q17, 68Q25, 68W25, 90C05, 90C22

Keywords and Phrases: NP-completeness, polynomial time, approximation algorithms, bin packing, unique games conjecture

Full text: dvi.gz 40 k, dvi 109 k, ps.gz 4168 k, pdf 401 k.