att_abstract={{The year 2012 marks the 40th anniversary of the publication of the
influential paper ``Reducibility among combinatorial problems'' by Richard
Karp, which first demonstrated the wide applicability of the
concept now known as NP-completeness, which had been introduced the previous
year by Stephen Cook and Leonid Levin, independently.
It also marks the 100th anniversary of the birth of Alan Turing,
whose invention of what is now known as the ``Turing machine'' underlay that
concept.  In this chapter, I shall briefly sketch the history and pre-history of
NP-completeness (with pictures), and provide a brief personal survey of the
developments in the theory over the
last 40 years and their impact (or lack thereof) on the practice and
theory of optimization.
I assume the reader is familiar with the basic concepts
of NP-completeness, P, and NP, although I hope the story will still
be interesting to those with only a fuzzy recollection of the definitions.
	att_categories={C_CCF.1, C_CCF.8},
	att_copyright={{DOCUMENTA MATHEMATICA }},
	att_copyright_notice={{The definitive version was published in  2012]. {{, Volume Extra Volume}}{{, 2012-08-19}}{{, www.math.uiuc.edu/documenta/}}
	att_tags={Nash,  Godel,  Cook,  Karp,  Levin,  Garey & Johnson},
	author={David Johnson},
	institution={{Documenta Mathematica, Extra Volume:
"Optimization Stories"
Marrtin Grotschel, Editor, pp }},
	title={{A brief history of NP-completeness, 1954-2012}},