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

This lecture introduces planar versions of 3SAT, in particular planar monotone rectilinear 3SAT and planar positive rectilinear 1-in-3SAT. But be careful: planar NAE 3SAT is polynomial.

We will prove these versions of planar SAT are NP-hard. Then we'll reduce them to problems on planar graphs and in 2D geometry:

• Planar X3C (Exact 3-Set Cover)
• Planar 3DM (3-Dimensional Matching)
• Planar Vertex Cover
• Planar (Directed) Hamiltonian Cycle
• Shakashaka (another Nikoli puzzle)
• Flattening fixed-angle chains (at a high level)

This class, we'll have a bunch of solved and open problems related to Hamiltonicity and other graph problems such as graph covering/packing, including several more games and puzzles that we could analyze.

We'll also cover a relevant piece of our new general “theory of gadgets” for puzzles with an agent/robot, and mention a useful new graph problem called “tree-residue vertex-breaking”.