A brief history of NP-completeness, 1954--2012
type: Item
instance of: scholarly article
title: A brief history of NP-completeness, 1954--2012
zbMATH Open document ID: 1260.68007
author: D. S. Johnson
published in: Documenta Mathematica
publication date: 2013-04-17T00:00:00Z
full work available at URL: 50 johnson-david.html
review text: Summary: The year 2012 marks the 40th anniversary of the publication of the influential paper ``Reducibility among combinatorial problems'' by \textit{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.
Mathematics Subject Classification ID: 68-03
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 6155104
zbMATH Keywords: NP-completeness
zbMATH Keywords: polynomial time
zbMATH Keywords: approximation algorithms
zbMATH Keywords: bin packing
zbMATH Keywords: unique games conjecture
describes a project that uses: Concorde
MaRDI profile type: Publication
Recommended article: NP-completeness: A retrospective
Recommended article: Q5703379
Recommended article: The Birth and Early Years of Parameterized Complexity
Recommended article: The NP-completeness column: An ongoing guide
Recommended article: Beyond NP
Recommended article: A historical note on the complexity of scheduling problems
description: scientific article; zbMATH DE number 6155104