[+] Nondeterministic Constraint Logic (NCL). Constraint graph, AND/SPLIT vertex, OR vertex, protected OR vertex, CHOICE vertex, redblue conversion, wire terminators, crossovers, grid graphs. Constraint Graph Satisfaction is NPcomplete, NCL is PSPACEcomplete. Reconfiguration 3SAT, slidingblock puzzles, sliding tokens, Rush Hour, hinged dissection, Sokoban, Push2F, rollingblock mazes, plank puzzles (River Crossing), dynamic map labeling, partial searchlight scheduling.  [Scribe Notes] [src]  
Tomorrow's lecture is about Constraint Logic. We saw the basic model in Lecture 1 to prove Rush Hour is PSPACEcomplete. Now we'll see the details of how Nondeterministic Constraint Logic (NCL) works, why it's PSPACEcomplete, and how we can reduce to a very small gadget set: planar graphs with just AND and protected OR vertices. Then we'll apply NCL to prove PSPACEcompleteness proofs for several different puzzles and problems:

Handwritten notes, page 1/8 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] 

Slides, page 1/54 •
[previous page] •
[next page] •
[PDF]
http://erikdemaine.org/papers/GPC/ Slides, page 1/54 • [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.