6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

We've proved hardness of a lot of puzzles, which can be viewed as 1-player games — the player represents the nondeterminism in move choices. This lecture is about games involving fewer or more players.

Zero-player games are essentially simulations, like a regular computer. The prototypical example here is Conway's Game of Life, which is PSPACE-complete or undecidable depending on whether you bound the board. A more modern example is Deterministic Constraint Logic, a version of constraint logic where edge-reversal order is deterministically defined (but many edges reverse in parallel), which is still PSPACE-complete.

In multiplayer games, we want to know whether a player (say, the first) has a winning strategy. In the worst case, all other players collude as a single entity, so the game reduces to two players. Thus we obtain 2-player games. We'll see many typical starting points for proving hardness of 2-player games, from QSAT itself to impartial/partizan game/seek/avoid SAT (from another amazing Schaefer paper). PSPACE-hard 2-player graph games include Kayles (essentially 2-player independent set), Geography (essentially 2-player longest path), Reversi/Othello, and bounded 2-player Constraint Logic (Bounded 2CL).

We'll briefly describe known results about 2-player and team games in the general theory of gadgets.