Tag Archives: Difficulty 7

First, an administrative note.  I wanted to call this site “Annotated NP-Complete Problems”, because the idea is that I’m going through the Garey&Johnson book and adding notes to each problem talking about how to do the reduction and how applicable it is for student assignments.  But that name is sort of taken already, and I don’t want to step on any toes or cause any confusion.  So I figured that I’d change the title now, before anyone finds out about the site.

And as I’ve been writing, these notes feel more like “discussions” than “short annotations” anyway, so I think this is a better title.

This is the last of the “core six” problems in the G&J book, as defined in Chapter 3.  There are several other problems presented in that chapter, with proofs, but since the point of this exercise is to get to the problems without proofs, I’m going to skip over them, and come back to them only if I need to (because they’re the basis for a future reduction, for example).

The problem: Partition (PART)

The definition: Given a set of integers A, can I fid a subset A’⊆A such that the sum of all of the elements in A’ is exactly half the sum of all of the elements in A?

(Alternately, given a set of integers A, can I split all of the elements of A into two subsets B and C, such that the sum of all of the elements in B is equal to the sum of all of the elements in C?)

(Alternately (this is the G&J definition), given any set A, where each element a∈A has a size s(z) that is a positive integer, can we find a subset A’ of A where the sum of the sizes of everything in A’ is exactly equal to the sum of the sizes of everything in A-A’?)

Example: Suppose A was the set {1,2,3,4,6}.  Then A’ could be {1,3,4}, forming a partition (A’ and A-A’ both sum to 8).  If instead, A was the set {1,2,3,4,5}, then no possible partition exists.  This may seem like a silly case (any set A where the sum of the elements is odd has no partition), but even if the sum of the elements of A is even, it’s possible that no partition exists- for example if A is {2,4,100}.

Note: Partition is one of my favorite NP-Complete problems, because the description is so easy, and it seems so simple.  It’s probably my go-to example if I want to explain this stuff to non-technical people in under a minute- pretend that the elements of A are weights, and the value of each element is the weight in ounces.  The partition problem asks “given this group of weights, and a “scales of justice” style scale, can you make the scale balance using all of the given weights?”.  It’s pretty surprising to most people that the only known way to answer that question basically boils down to “try all possible combinations of arranging things on the scale”

The reduction: From 3DM.  G&J provide the reduction on pages 61-62.  The basic idea is to have one element in A for each element in M, and to represent the elements in A as binary numbers that have 1’s in positions corresponding to which element from W, X, and Y we get the triple from.  The number is set up so that we have a maximum possible value of the sum of all of these elements in A.  They then add two “extra” elements to A so that each side of the partition (elements of M that make a matching, and everything else) will add up to the same value

Difficulty: 7.  The idea of using binary numbers to keep track of “positions” in a list is tricky, but comes up in lots of places.  If students have seen that idea before, this becomes a hard but doable problem.  If students haven’t seen that idea before, I’d make this a 9.