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

Lecture 3 Video [previous] [next]

[+] 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]