# 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 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. 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).
 No support for video detected. Please use an HTML5 browser. 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]