Today we examined some other types of problem reduction that we use when showing that problems are NP-Complete.

We defined two problems:

Partition:  Given a set of integers, is it possible to divide the set into two subsets so that each subset sums to exactly 1/2 the sum of the original set?

Subset Sum:  Given a set of integers and a target integer k, does the set have a subset that sums exactly to k?

Both of these are obviously decision problems, and both are clearly in NP.  (Situation check - make sure you understand the difference between saying a problem is in NP, and saying the problem is NP-Complete.  This distinction is essential.)


Let's suppose for the moment that we know that Partition is NP-Complete (it is), and see how we could use that knowledge to prove that Subset Sum is NP-Complete.  It turns out that this is extremely easy because the new problem (SS) is a generalization of the known problem (Part).    Or putting it another way, Partition is a special case of Subset Sum.  Transforming an instance of Partition into an instance of Subset in an answer-preserving form takes no effort at all - every instance of Partition is already an instance of Subset Sum.

This illustrates a general principle: if a new problem (in the class NP) is a generalization of a known NP-Complete problem, then the new problem is also NP-Complete.


Now let's suppose that we know Subset Sum is NP-Complete, but we don't know about Partition.  Can we use Subset Sum to show that Partition is NP-Complete?  Well, we can't use the principle we just learned - we can't automatically transform an instance of a general problem (SS) to a special case (Part).   We can still find a reduction ... it just takes a little bit more work.

Let's think about what we start with: an instance of Subset Sum, i.e. a set of integers and a target integer k.  We want to transform this into an instance of Partition in such a way that the Yes/No answer is preserved.  Suppose the answer to the instance of SS is Yes - that means there IS a subset that sums to k.  If we let T be the total sum of the set, then the other subset (i.e. all the elements not in the set that sums to k) must sum to T-k.  We need to "do something" to the original set of integers so that we have a set that can be partitioned into two equal sets.

There are lots of possibilities - one is to add a single element to the set, with value 2k-T.  Now the sum of the total set is 2k.  Let us ensure that the transformation IS answer-preserving.  First, we see that a Yes answer to SS on the original set implies a Yes answer to Part on the modified set - the original subset that sums to k still exists, and the remaining set (augmented by the new element) also sums to k.  Now suppose that the answer to Part on the augmented set is Yes.  This means that the two subsets both sum to k ... and since the new element can only be in one of the subsets, the other consists entirely of elements from the original set ... so the answer to SS on the original set is Yes.

Thus we see that Subset Sum reduces to Partition.


We finished with another illustration of reduction, involving a third problem:

Within 10 Subset Sum:  Given a set of integers and a target integer k, does the set have a subset that sums to within 10 of k (i.e. sums to any of the values k-10, k-9, ... k+9, k+10)

This looks like it might be easier than Subset Sum, because we are requiring less precision.  Also, it is not immediately clear how to transform an instance of SS into an instance of W10SS in an answer preserving way, since a Yes answer in W10SS does not obviously imply a Yes answer in SS.  However, there are at least two ways to do the transformation that get us what we want:

If we multiply all elements of the set and k by 100, then all subsets of the modified set sum to values that end in "00" - thus there is no way to get within 10 of a target value without hitting it exactly.
If the answer to the original instance of SS is Yes, the obviously the answer to W10SS on the modified set is Yes.  If the answer to W10SS on the modified set is Yes, then (by the argument just given) it must hit the target 100k exactly - and the same set of elements in the original set must hit the target k exactly, so the answer to SS on the original set is also Yes.  Thus SS reduces to W10SS, and we conclude that W10SS is NP-Complete.

We will discuss another way to do this reduction on Monday.  

For now, an important lesson to learn is that sometimes, being willing to accept some inexactness in our solution (that is "can we get within 10 of a perfect solution?") does not make the problem any easier.  However, for some other NP-Complete problems we can find polynomial-time algorithms that DO get close to the perfect solution ... the class of NP-Complete problems has more structure and variablility than we can explore in this course.