Geodesic
A brief history of NP-completeness, 1954--2012
Documenta mathematica, Optimization Stories (2012), pp. 359-376.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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.
Classification : 68-03, 68Q17, 68Q25, 68W25, 90C05, 90C22
Keywords: NP-completeness, polynomial time, approximation algorithms, bin packing, unique games conjecture 
@article{DOCMA_2012__S3__a8,
     author = {Johnson, David S.},
     title = {A brief history of {NP-completeness,} 1954--2012},
     journal = {Documenta mathematica},
     pages = {359--376},
     publisher = {mathdoc},
     volume = {Optimization Stories},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a8/}
}
TY  - JOUR
AU  - Johnson, David S.
TI  - A brief history of NP-completeness, 1954--2012
JO  - Documenta mathematica
PY  - 2012
SP  - 359
EP  - 376
VL  - Optimization Stories
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a8/
LA  - en
ID  - DOCMA_2012__S3__a8
ER  - 
%0 Journal Article
%A Johnson, David S.
%T A brief history of NP-completeness, 1954--2012
%J Documenta mathematica
%D 2012
%P 359-376
%V Optimization Stories
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a8/
%G en
%F DOCMA_2012__S3__a8
Johnson, David S. A brief history of NP-completeness, 1954--2012. Documenta mathematica, Optimization Stories (2012), pp. 359-376. http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a8/