@techreport{TD:100899, 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_authors={dj1576}, 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_donotupload={}, att_private={false}, att_projects={}, att_tags={Nash, Godel, Cook, Karp, Levin, Garey & Johnson}, att_techdoc={true}, att_techdoc_key={TD:100899}, att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100899_DS1_2012-09-05T17:43:19.218Z.pdf}, author={David Johnson}, institution={{Documenta Mathematica, Extra Volume: "Optimization Stories" Marrtin Grotschel, Editor, pp }}, month={August}, title={{A brief history of NP-completeness, 1954-2012}}, year=2012, }