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

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

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)

Video Player is loading.

Current Time 0:00

Duration -:-

Loaded: 0%

Stream Type LIVE

Remaining Time -:-

Download Video: 360p, 720p

Handwritten notes, page 1/5 • [previous page] • [next page] • [PDF]
Video times: • 0:15–28:48

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

Slides, page 6/37 • [previous page] • [next page] • [PDF]
Video times: • 40:57–41:44

Figure 1 of http://erikdemaine.org/papers/CCCG2000b/

Slides, page 6/37 • [previous page] • [next page] • [PDF]

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

Prof. Erik Demaine TAs: Sarah Eisenstat, Jayson Lynch

Lecture 7 Video [previous] [next]