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]

Lecture 2 Video     [previous] [next]

[+] 3-partition I. 2-partition vs. 3-partition; variations (Subset Sum, Numerical 3-dimensional matching, 3DM, X3C); weakly vs. strongly NP-hard; pseudopolynomial vs. polynomial. Multiprocessor scheduling, rectangle packing, edge-matching puzzles, jigsaw puzzles, polyform packing puzzles, packing squares into a square. Scribe Notes [src]
This lecture introduces my favorite (and a generally lesser known) starting point for NP-hardness reductions, called 3-partition. This problem is particularly useful when you have a problem that involves adding up numbers, even when those numbers must be encoded in unary (a common feature of many puzzles). We'll discuss many variations of the problem:
  • 2-partition: Partition integers into two sets of equal sum
  • Subset Sum: Select integers to equal a target sum
  • 3-partition: Partition n integers into n/3 triples of equal sum
  • Numerical 3-dimensional matching: Integers are of three different types, and each triple must have all three types.
  • 3-dimensional matching: A generalization to tripartite hypergraphs.
  • Exact cover by 3-sets: A generalization to hypergraphs.

2-partition vs. 3-partition is an example of the weak vs. strong NP-hardness dichotomy, and on the algorithmic side, the pseudopolynomial vs. (weakly) polynomial dichotomy. We'll see weak and strong NP-hardness proofs, by reductions from 2-partition and 3-partition respectively, for two problems:

  • multiprocessor scheduling
  • packing rectangles into a rectangle

Next we'll see a fun series of reductions between different puzzles, starting from 3-partition / rectangle packing to establish strong NP-hardness.

  • edge-matching puzzles ("signed" like lizards, and "unsigned" like Eternity II)
  • jigsaw puzzles
  • polyomino packing puzzles (like Eternity)

Finally, we'll see how to prove strong NP-hardness of packing squares into a square. This is a handy result that we'll use as the basis for another reduction next lecture.

Download Video: 360p, 720p

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

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

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

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

The video above should play if your web browser supports either modern Flash or 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.