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
Proving that Super Mario Brothers (even with glitches) is NP-Hard is such a fun example! I'm glad you included it :)
ReplyDeleteSurprising that the draft book says basically nothing about quantum computers and BQP.
ReplyDeleteThe 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