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 is

Computational Intractability: A Guide to Algorithmic Lower Bounds

LANCE: That sounds similar to Garey and Johnson's classic

Computers and Intractability: A Guide to the Theory of NP-Completeness

BILL: Indeed. DGH is a sequel to Garey and Johnson

LANCE: 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 1979

LANCE: 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 of

Disk Packing: Given a set of disks and a target square, can you place the disks so that they do not overlap and all of their centers lie within the square This is Strongly NP-hard. 

Mate-in-1: Given a position in Settlers of Catan, can the player who is about to go win? This is NP-complete

Losing Checkers: Given a position in Checkers, is there a move that forces your opponent to win, is NP-complete. This is an important problem in case you play Checkers with a  Wookie, see here.

Super Mario Brothers and Many other Nintendo Games: Given a position in the game, and a level, can the player get to that level. This is NP-complete. (There are versions that are PSPACE-complete and versions that are undecidable)

Some use the machinery developed since G & J to show lower bounds on approximation:

VC with vertices of degree \(\le 3\): If there is a polytime \((\frac{145}{144}-\epsilon)\)-approx then P=NP

We have a chapter on the Unique Games Conj--uh, uh, Theorem. 

We look BELOW NP: 3SUM-hardness, APSP-hardness (these are both a bit outdated), streaming algorithms, online algorithms, others.

We look ABOVE NP: #P, ETR,  

LANCE: What's ETR?

BILL: Existential Theory of the Reals is the following problem: Given a sentence of the form 

\((\exists x_1)(\exists x_2)\cdots(\exists x_n)[ C_1 \wedge \cdots \wedge C_k]\)

where each \(C_i\) is a polynomial equality or inequality in \(x_1,\ldots,x_n\)

is this sentence, with the quantifier going over the reals, true?

Tarski proved ETR is decidable. ETR is known to be NP-hard and is thought to be harder than NP. 

A problem is ETR-complete if it is equivalent to ETR. This is a way to classify some problems that involve reals that were hard to classify with more traditional classes. For example, the Art Gallery Problem (how many guards to you need) is ETR-complete

LANCE: What else do you have that's above NP? 

BILL:  Poly Hierarchy, PSPACE, and even undecidability.

LANCE: Are there really NEW results about undecidability?

BILL: There are some video games where questions about winning are undecidable. I doubt Turing knew that. One of them is called braid (see here).

LANCE: Don't you have whole chapters devoted to the non-defunct Exponential Time Hypothesis and the 3-SUM conjecture?

Bill: Also the APSP conjecture. Are these now-defunct conjectures still worth studying? I did a blog post on that here. Do you read my blog posts?

LANCE: Do you read mine?

BILL: Fair point.

LANCE: Despite having three chapters obsolete, the rest of the book sounds great. Where can I get it?

BILL: You can buy it on Amazon, see here. You can buy it at MIT press here. You can download a prior draft here.