6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 13 Video     [previous] [next] [completion form]

[+] 0- and 2-player games. 0-player games: Conway's Game of Life is undecidable, Deterministic Constraint Logic (DCL) is PSPACE-complete. Bounded 2-player games are PSPACE-complete: impartial/partizan game/avoid/seek SAT, Kayles, Geography, Reversi/Othello, bounded 2-player Constraint Logic (Bounded 2CL).

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 have a slew of problems related to Constraint Logic, 2-player games, stochastic games, and other unusual types of games. We'll also briefly cover the last known results in the general theory of gadgets.

Download Video: 360p, 720p

Handwritten notes, page 1/6[previous page][next page][PDF]

Handwritten notes, page 1/6[previous page][next page][PDF]

Slides, page 1/39[previous page][next page][PDF]

Slide from Lecture 1. http://​erikdemaine.org/​papers/​GPC/​

Slides, page 1/39[previous page][next page][PDF]