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 4 Video     [previous] [next]

[+] SAT. SAT, Circuit SAT, CNF SAT, 3SAT, 3SAT-4, Monotone 3SAT, 2SAT, Max 2SAT, Horn SAT, Dual-Horn SAT, DNF SAT, 1-in-3SAT / exact-1 3SAT, NAE 3SAT / Not-All-Equal 3SAT, Schaefer's Dichotomy Theorem, 2-colorable perfect matching. Pushing blocks: Push-1, Push-∗ PushPush, PushPushPush, Push-F, Push-X, Sokoban. [Scribe Notes] [src]

Satisfiability, particularly 3SAT and its many variations, is the prototype NP-complete problem, forming the starting point for almost all NP-complete problems. This class gives an overview of all the important variations, particularly the NP-complete ones, but also some close cousins which are polynomially solvable (so no good for NP-completeness!).

Then we'll see a few first examples of NP-hardness proofs based on 3SAT, centered around pushing block puzzles popular in many video games (and with practical applications to warehouse motion planning). After introducing a variety of different such puzzles, such as Sokoban, we'll prove NP-hard Push-∗ and Push-1 and PushPush-1 (first in 3D, then in 2D).

Download Video: 360p, 720p

Handwritten notes, page 1/6[previous page][next page][PDF]

Handwritten notes, page 1/6[previous page][next page][PDF]

Slides, page 1/13[previous page][next page][PDF]

Slides, page 1/13[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.