6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch


[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza]

Lecture 7 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 [Scribe Notes] [src]

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]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.