Wednesday, September 21, 2022

POSTED UPDATED VERSION OF Computers and Intractability: A guide to Algorithmic Lower Bounds posted (New title)

We have posted a revised version of 


Computational Intractability: A Guide to Algorithmic Lower Bounds

by Demaine-Gasarch-Hajiaghayi

The book is here.

(For the original post about it, edited it to use the new title (see below), see HERE.) 


We  changed the title (the title above is the new one) 

since the earlier title looked too much

like the title of Garey's and Johnson's classic. While that was intentional we 

later felt that it was too close to their title and might cause confusion. 

Of course changing the title might also cause confusion; however, 

this post (and we will email various people as well) will stem that confusion. 


We welcome corrections, suggestions and comments on the book. Email us at hardness-book@mit.edu


3 comments:

  1. Proving that Super Mario Brothers (even with glitches) is NP-Hard is such a fun example! I'm glad you included it :)

    ReplyDelete
  2. Surprising that the draft book says basically nothing about quantum computers and BQP.

    ReplyDelete
    Replies
    1. The current version is 526 pages (longer than the one posted) so we had to make some choices as to what to include and not include.

      Delete