PineWikiThe SUBSET SUM problem is defined by the language
{ (S,k) : S is a set of integers that has a subset S' with ∑S' = k }.
We can show that SUBSET SUM is NP-hard by reduction from INDEPENDENT SET (see PvsNp for definitions of these terms).
Start with the graph G and the desired size of the independent set k. Choose a base b that is larger than |V| (to avoid carries in the sum); we will represent our numbers in base b. Number the edges from 1 to m.
For each vertex v, include in S the number ∑i in Δ(i) bi + 1, where Δ(i) is the set of edges that have v as an endpoint. For each edge i, include bi. Let the target sum k' = ∑i in E bi + k.
Example: let G have edges ab, ac, ad, bc, and cd and suppose k = 2. Then the set consists of the nine numbers (read across rows):
Edge: ab ac ad bc cd - a 1 1 1 0 0 1 b 1 0 0 1 0 1 c 0 1 0 1 1 1 d 0 0 1 0 1 1 ab 1 0 0 0 0 0 ac 0 1 0 0 0 0 ad 0 0 1 0 0 0 bc 0 0 0 1 0 0 bd 0 0 0 0 1 0 k' 1 1 1 1 1 2
How can we construct the target? We need to take exactly k vertices to get a k in the last digit of the sum. We can't take more than one vertex per edge, or we'll get a 2 in one of the earlier digits---this means that whatever vertices we do take form an independent set, and thus if we do get k' then an independent set of size k exists.
Conversely, summing up an independent set fills it some (but generally not all) of the digits except the end; the numbers corresponding to each edge let us fill in the gaps, showing that if an independent set of size k exists we can construct k'.
For example, in the case above we sum
b 100101 + d 001011 + ac 010000 = k' 111112
and get k' from the independent set {b, d}.
Since we've shown that k' can be made as a sum of elements in S if and only if G has an independent set of size k, and since the construction is easily seen to be polynomial, we have a poly-time reduction from INDEPENDENT SET to SUBSET SUM, which shows that SUBSET SUM is NP-hard. It's also in NP (guess the correct subset and verify it in poly time), so it's NP-complete.
PARTITION
An even simpler version of SUBSET SUM is PARTITION, which asks if there is a subset of S with total value ½∑x in S x. It's easy to reduce PARTITION to SUBSET SUM (set k = ½∑x in S x), but this doesn't tell us much about PARTITION; instead we want a reduction in the other direction. The basic trick is to add a new element y to S so that any even split of S ∪ {y} contains a subset that has total weight k without containing y or that has total weight k+y and contains y. The details are left as an exercise.