6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch

[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 18 Video     [previous] [next]

[+] 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 (2CL). [Scribe Notes] [src]

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 (2CL).

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]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.