0xDE (11011110) wrote,

Johnson on NP-completeness

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...
Tags: complexity theory, exponential algorithms, papers
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment