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

[+] SAT Reductions. Nintendo games (Super Mario World, glitches, Legend of Zelda, Metroid, Donkey Kong Country, Pokémon); Conway's Phutball (Philosopher's Football), mate-in-1, Checkers; cryptarithms (alphametics); origami flat-foldable crease patterns; vertex-disjoint paths (Numberlink)

This lecture is filled with NP-hardness reductions from 3SAT, including:

Nintendo games
- Super Mario Bros. (beyond Lecture 1)
- Legend of Zelda
- Metroid
- Donkey Kong Country
- Pokemon
Conway's Phutball (Philosopher's Football), where mate-in-1 is NP-hard unlike Checkers
Cryptarithm / alphametic puzzles
Vertex-disjoint paths
- in a graph
- in a planar graph
- in a rectangle
Origami crease patterns (flat foldability)

Don't worry if you don't know any of the games — I will introduce each.

Download Video: 360p, 720p

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

Slides, page 1/46 • [previous page] • [next page] • [PDF]

http://arxiv.org/abs/1203.1895

Slides, page 1/46 • [previous page] • [next page] • [PDF]