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:

Current Time 0:00
Duration -:-
Loaded: 0%
Stream Type LIVE
Remaining Time -:-
 
1x
  • Chapters
  • descriptions off, selected

    Download Video: 360p, 720p

    Handwritten notes, page 4/5 • [previous page] • [next page] • [PDF]
    Video times: • 50:47–64:09

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

    Slides, page 1/36 • [previous page] • [next page] • [PDF]
    Video times: • 2:58–16:45

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