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 6 Video     [previous] [next] [completion form]

[+] Circuit SAT. Dual-rail logic vs. binary logic; Akari/Light Up, Minesweeper (consistency and inference); planar Circuit SAT; Candy Crush / Bejeweled

This lecture starts with a distinction between two key SAT reduction styles:

  • Dual-rail logic: variables + clauses (most proofs we've seen)
  • Binary logic: wires + splitters + clauses (crease pattern proof)
  • Circuit SAT: wires + splitters + universal gates
Then we will see a few proofs in the Circuit SAT style:

Download Video: 360p, 720p

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

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

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

http://​arxiv.org/​abs/​1203.1895

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