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

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