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 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. [Scribe Notes] [src]

Tomorrow's 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:

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]

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.