[+] 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. | |||||
In this class, we'll talk about a new level of planar 3SAT called linked planar 3SAT. This problem is motivated by the type of planarity needed in e.g. the Super Mario Bros. NP-hardness proof:
We'll also have many solved and open problems related to planar SAT and circuit SAT and their many variations. Finally, we'll plan a bit for what to do with all the solutions to open problems we've been coming up with: research papers, final projects, etc. |
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] |