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

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