Demaine-Gasarch-Hajiaghayi have written a book that is a sequel to Garey and Johnson

LANCE: You should take a break from all the AI stuff and talk about your book!BILL: I will! But its not my book its co-authored with Erik Demaine and Mohammad Hajiaghayi. The title isComputational Intractability: A Guide to Algorithmic Lower BoundsLANCE: That sounds similar to Garey and Johnson's classicComputers and Intractability: A Guide to the Theory of NP-CompletenessBILL: Indeed. DGH is a sequel to Garey and JohnsonLANCE: But so much has happened since 1979.BILL: Yes. That's why the book is over 500 pages and still does not cover everything since 1979LANCE: So what IS in the book?BILL: The main question that drives complexity theory (and many other fields) is the question: Given a problem, how hard is it?LANCE: Oh, You mean like P and NP!BILL: Yes, but there is more! We cover P and NP: Many problems are proven NP-complete. Some are on Puzzles and Games. Examples of NP-Complete Problems that you might not have heard ofDisk Packing: Given a set of disks and a target square, can…

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town