Lecture 3 in 6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Lecture 3 Video [previous] [next] [completion form]

[+] 3-partition II: edge-unfolding polyhedra, snake cube puzzle, disk packing, Clickomania, Tetris, 1-planarity, GeoLoop/Ivan's Hinge.
2-partition: ruler folding, simple map folding.

This lecture includes a second (and final) bunch of strong NP-hardness reductions from 3-partition:

Edge-unfolding polyhedra: A reduction from square packing (from L02). [Abel & Demaine 2011]
Snake cube puzzle: Fold a chain of cubes with 90° bends at given locations into a larger cube. [Abel, Demaine, Demaine, Eisenstat, Lynch, Schardl 2013]
Disk packing: Pack disks into a square (motivated by origami design). [Demaine, Fekete, Lang 2010]
Clickomania: Delete monochromatic groups of size > 1 to erase everything. [Biedl, Demaine, Demaine, Fleischer, Jacobsen, Munro 2000]
Tetris: Survive given piece sequence from given initial configuration. [Breukelaar, Demaine, Hohenberger, Hoogeboom, Kosters, Liben-Nowell 2004]
1-planarity: Drawing a graph so that each edge crosses at most one other edge. [Grigoriev, Bodlaender 2007]
GeoLoop / Ivan's Hinge (piano-hinged dissections) [Abel, Demaine, Demaine, Horiyama, Uehara 2014]

Plus we'll see a couple of weak NP-hardness reductions from 2-partition:

Ruler folding: Fold a carpenter's ruler to fit inside a 1D box. [Hopcroft, Joseph, Whitesides 1985]
Simple map folding: Fold a square piece of paper along one line at a time to achieve specified creases. [Arkin,Bender, Demaine, Demaine, Mitchell, Sethia, Skiena 2000]

We'll focus mainly on problem solving — we have many solved and open problems related to SAT. As usual, we'll also briefly review the progress on past open problems (and you're welcome to continue on those). I'll also briefly describe a software tool for drawing grid-based figures, called SVG Tiler, which we've used for drawing lots of hardness reductions.