I was interested to see David Johnson's new survey, A Brief History of NP-Completeness, 1954–2012, but also a bit disappointed after reading it, because if you believe what it says, the only things that have happened in this subject since the late 1970s have concerned approximation. There was nothing in it about exponential time algorithmics, parameterized complexity, the exponential time hypothesis, the empirical success of SAT solvers...

ETA: An updated version here describes where it was published (in a book distributed to attendees of ISMP 2012). And DSJ tells me that part of the reason for the narrow focus of the later part of the survey is that it was already five pages over the limit...




Comments:

ext_887241:
2012-09-02T02:12:25Z

To be fair, the survey does say "It would be impossible, in the limited space left to me, to give a thorough history of the developments in the theory of NP-completeness since the 1970s, so in this section I shall restrict myself to just one thread...."