# 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] [Accessibility]

## Lecture 17 Video     [previous] [next]

 [+] Nondeterministic Constraint Logic (NCL). Constraint graph, AND/SPLIT vertex, OR vertex, protected OR vertex, CHOICE vertex, red-blue conversion, wire terminators, crossovers, grid graphs. Constraint Graph Satisfaction is NP-complete, NCL is PSPACE-complete. Reconfiguration 3SAT, sliding-block puzzles, sliding tokens, Rush Hour, hinged dissection, Sokoban, Push-2F, rolling-block 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 PSPACE-complete. Now we'll see the details of how Nondeterministic Constraint Logic (NCL) works, why it's PSPACE-complete, 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 PSPACE-completeness proofs for several different puzzles and problems: Reconfiguration 3SAT Sliding-block puzzles Sliding tokens Rush Hour Hinged dissection reconfiguration Sokoban Push-2F Rolling-block mazes Plank puzzles / River Crossing Dynamic map labeling Partial searchlight scheduling
 No support for video detected. Please use an HTML5 browser. Download Video: 360p, 720p 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] Slides, page 1/54 • [previous page] • [next page] • [PDF]