6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

This lecture introduces Linked Planar 3SAT. Linked planar 3SAT is very useful for reductions for Mario-style games where an agent needs to traverse variable gadgets followed by clause gadgets without needing a crossover.

In Linked Planar SAT, we have planar bipartite graph of variables and clauses, and also have cycle containing all of the variables followed by all of the clauses. We'll show this is NP-complete.

We'll also introduce the door opening and door closing as an application of linked planar 3SAT, and use it to simply NP-hardness proofs of Mario, Zelda, Pokémon, and other games.