Question

Show that the partition problem is polynomially reducible to the decision version of the knapsack problem. Please give details. This problem has been "solved" before but the answer given made no sense at all.

Answer 1

Here is a straightforward algorithm that takes an instance of the Simple Knapsack problem and returns an equivalent instance of the Set Partition problem:

Input: Simple Knapsack problem w1, w2, ..., wn and capacity C
Output: A Set Partition problem that's equivalent to the input Knapsack Problem.

1. set S = w1 + w2 + ... + wn

2. if (C >= S/2) set wn+1 = 2*C - S
else set wn+1 = S - 2*C

3. return Set Partition problem w1, w2, ..., wn, wn+1

We should prove that the given 0/1 Knapsack problem and the Set Partition problem produced by our algorithm are equivalent.

Proposition: Given Simple Knapsack problem w1, w2, ..., wn and capacity C, the above algorithm returns an equivalent Set Partition problem.
Proof: Let S = w1 + w2 + ... + wn. First, we'll show that if the Knapsack problem is true, so is the set partition problem. Suppose that some subset of weights fills the knapsack to capacity C. The sum of all the wieghts not in the knapsack is S - C. If C ≥ S/2 the partition problem returned by the algorithm adds weight wn+1 = 2*C - S, so adding wn+1 to the set of weights not in the knapsack gives gives a set of total weight S - C + 2C - S = C, and we have a partition into two sets of weight C. If C < S/2 the partition problem returned by the algorithm adds weight wn+1 = S - 2*C, so adding wn+1 to the set of weights in the knapsack gives a set of total weight C + S - 2C = S - C, which is equal to the set of weights not in the knapsack. Thus if the original knapsack problem can be solved, so can the returned partition problem.

Next we'll show that if the Partition Problem is true, so is the Knapsack problem. Suppose that the n+1 wieghts in the partition problem can be partitioned into two sets of equal weight. If C ≥ S/2 the partition problem returned by the algorithm adds weight wn+1 = 2*C - S, so the sum of all weights in the partition problem is S + 2C - S = 2C. Thus, both partition sets sum to C, and whichever doesn't have the weight wn+1 is a solution to the original knapsack problem. If C < S/2 the partition problem returned by the algorithm adds weight wn+1 = S - 2*C, so the sum of all weights in the partition problem is S + S - 2*C = 2*(S - C). Thus, both partition sets sum to S - C, and if we remove weight wn+1 from whichever set has it, the remaining weights sum to S - C - (S - 2*C) = C and thus provide a solution to the original knapsack problem. Thus if the returned partition problem can be solved, so can the original knapsack problem.

We can't have one problem solvable without the other one being solvable as well, so either both are solvable or neither are solvable. Thus the two problems are equivalent.

Clearly, our algorithm takes polynomial time. Thus, Simple Knapsack is polynomial time reducible to Set Partition, which means among other things that if we can solve Set Partition in polynomial time we can also solve Simple Knapsack in polynomial time.