A brief history of NP-completeness, 1954–2012

Abstract

The year 2012 marks the 40th anniversary of the publication of the influential paper "Reducibility among combinatorial problems" by R. M. Karp [in: Complexity of Computer Computations 1972. New York: Plenum Press. 85--103 (1972)]. This paper was the first to demonstrate 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. 2012 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.