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

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 7 Video     [previous] [next] [completion form]

[+] Planar SAT. Planar 3SAT, planar monotone rectilinear 3SAT, planar positive 1-in-3SAT, planar NAE 3SAT (polynomial!), planar X3C, planar 3DM; planar vertex cover, planar (directed) Hamiltonian cycle, Shakashaka, flattening fixed-angle chains

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:

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”.

Download Video: 360p, 720p

Handwritten notes, page 1/5[previous page][next page][PDF]

Handwritten notes, page 1/5[previous page][next page][PDF]

Slides, page 1/37[previous page][next page][PDF]

Figure drawn by Erik Demaine based on Figure 4 of http://​dx.doi.org/​10.1137/​0211025

Slides, page 1/37[previous page][next page][PDF]