PSPACE-complete

Just as NP has its hardest representatives (the NP-complete problems), PSPACE has its own champions. A problem is PSPACE-complete if it is in PSPACE and every problem in PSPACE reduces to it, so it is, in a precise sense, the hardest problem you can still solve with polynomial memory. Crack a single PSPACE-complete problem efficiently and you would crack all of PSPACE, including all of NP and P along the way. These are the problems that mark the true ceiling of polynomial space.

Formally, B is PSPACE-complete if B is in PSPACE and every language A in PSPACE reduces to B by a polynomial-time (many-one) reduction. The flagship example is TQBF, the truth of quantified boolean formulas: deciding whether a sentence like 'exists x, for all y, exists z, phi(x,y,z)' is true. It is PSPACE-complete because the alternating exists/for-all structure exactly mirrors how a PSPACE machine can explore and verify with polynomial memory. A whole genre of two-player games is PSPACE-complete too: generalized geography, generalized versions of Go, Hex, and Reversi on n-by-n boards, the puzzle Sokoban, and many more. The common thread is the question 'does the player to move have a winning strategy?', which is naturally a chain of quantifiers (I have a move such that for every reply I have a move ...).

PSPACE-complete problems pin down the meaning of PSPACE the way SAT pins down NP. They are believed to be strictly harder than every NP problem (since PSPACE is conjectured to strictly contain NP), but that, like nearly everything in this area, is unproved. Caveat: it is easy to mistake a game for being merely NP-like because you can verify a single line of play quickly, but winning requires reasoning about all of the opponent's responses, the for-all quantifier, which is what pushes these problems out of NP and up into PSPACE. And as always, PSPACE-hard is broader than PSPACE-complete: a PSPACE-hard problem need not itself lie in PSPACE.