S1wi = ∑
jS2wj Definition
Given a collection of numbers, w1,…,wn. There exist two disjoint set S1,S2 ⊂{1,…,n},
such that ∑
iS1wi = ∑
jS2wj
Polynomial Certifier
Given a collection of numbers, w1,…,wn. There exist two disjoint set
S1,S2 ⊂{1,…,n}, such that ∑
iS1wi = ∑
jS2wj
Reduction from Subset Sum from simple case to general case
Consider an arbitrary instance of Subset Sum with numbers w1,…,wn and target sum W. We will construct an equivalent instance of Number Partitioning as following:
Let Wtotal = ∑ i=1nwi be the total sum of all numbers. Add two numbers wn+1 = W + m and wn+2 = Wtotal + m-W, where m is a natural number. Note that the sum of all (n + 2) numbers is Wtotal + W + m + Wtotal + m-W = 2Wtotal + 2m.
Claim 4.17.2.1. Subset Sum ≤p Number Partitioning. (Subset Sum is a special case
of Number Partitioning)
If an instance of Subset Sum holds if and only if an instance of Number
Partitioning Problem also holds.
⇒
Proof. Suppose that we have w1,…,wn, and there exits a set Wans = {wi|1 ≤ i ≤ n}, of which elements adds up to W. From the construction above, we create two numbers wn+1 = W + m and wn+2 = Wtotal + m - W. Hence, we can divide those number into two groups:
We can immediately tell that the sum of elements in S1 is (W +Wtotal+m-W) = Wtotal+m, and the sum of elements in S2 is Wtotal -W + W + m = Wtotal + m. Therefore, the number partitioning holds. __
⇐
Proof. Suppose that Number Partitioning problem holds, then there is a partition S1,S2 that have equal sums, Wtotal+m. Consider S1 = Wans+wn+2. Since wn+2 = Wtotal + m - W we can easily tell that elements of Wans adds up to W. Hence, a set Wans must exist, and thus, Subset Sum holds. __