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

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova


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

Lecture 5 Video     [previous] [next]

[+] 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:

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/36[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/36[previous page][next page][PDF]