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

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.

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:

1. visit all the variables in some order to make choices,
2. affect all the incident clauses, and then
3. visit all the clauses in some order to check that they're all satisfied.

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.