6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 4 Video     [previous] [next] [completion form]

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

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]