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 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.
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]