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

## Prof. Erik Demaine     TAs: Sarah Eisenstat, Jayson Lynch

[Home] [Lectures] [Problem Sets] [Project] [Open Problems] [Piazza] [Accessibility]

## 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]
 No support for video detected. Please use an HTML5 browser. Download Video: 360p, 720p Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] Handwritten notes, page 1/8 • [previous page] • [next page] • [PDF] Slides, page 1/41 • [previous page] • [next page] • [PDF] Slides, page 1/41 • [previous page] • [next page] • [PDF]