[+] 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.  
This 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] 