[+] 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:
Don't worry if you don't know any of the games — I will introduce each. |
Handwritten notes, page 1/6 •
[previous page] •
[next page] •
[PDF]
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] |