|
Using a similar reduction, ABC-partition can be reduced to 3-partition.
=== Reduction from ABCD-partition to ABC-partition ===
We are given an instance of ''ABCD''-partition with ''m'' elements per set, threshold ''T'', and sum ''mT.'' We construct an instance ABC-partition (which for clarity we will call XYZ-paritition) as follows:
* For each ''a<sub>i</sub>'' in A, the set X contains a "regular" element ''x<sub>i</sub>'' = 5T+''a<sub>i</sub>''.
* For each ''b<sub>j</sub>'' in B, the set Y contains a "regular" element ''y<sub>j</sub>'' = 5T+''b<sub>j</sub>''.
* For each pair of elements c<sub>i</sub> in C and d<sub>j</sub> in D, the set Z contains two "pairing" elements: z<sub>ij</sub> = 6T - c<sub>i</sub> - d<sub>j</sub> and z<sub>ij</sub>' = 5T + c<sub>i</sub> + d<sub>j</sub>. All in all there are m<sup>2</sup> pairing elements, summing up to 11T*m<sup>2</sup>.
* Additionally, B contains 8m<sup>2</sup>-3m "filler" elements, with size 20T, and total sum (8m<sup>2</sup>-3m)*20T.
* All in all, B contains 24m<sup>2</sup>-3m = 3(8m<sup>2</sup>-m) elements, with sum (64T+4)*(8m<sup>2</sup>-m).
* The threshold for the 3-partition instance is 64T+4; note that the sizes of all elements in B are in (16T+1,32T+2).
Given an ABCD-partition, we construct an XYZ-partition as follows:
* For each 4-set {a<sub>1</sub>,b<sub>2</sub>,c<sub>3</sub>,d<sub>4</sub>} with sum T, we construct a 3-set {x<sub>1</sub>,y<sub>2</sub>,z<sub>34</sub>} with sum 4*(5T+a<sub>1</sub>+5T+a<sub>2</sub>+6T-a<sub>1</sub>-a<sub>2</sub>)+1+1+2=64T+4 and another 3-set {w<sub>3</sub>,w<sub>4</sub>,u<sub>12</sub>'} with sum 4*(5T+a<sub>3</sub>+5T+a<sub>4</sub>+5T+a<sub>1</sub>+a<sub>2</sub>)+1+1+2=64T+4. These sets contain all 4m regular elements and 2m matching pairs of pairing elements.
* From the remaining elements, we construct 3-sets {u<sub>ij</sub>,u<sub>ij</sub>',filler} with sum 4*(6T-a<sub>i</sub>-a<sub>j</sub>+5T+a<sub>i</sub>+a<sub>j</sub>+5T)+2+2=64T+4.
Conversely, given a 3-partition of B, the sum of each 3-set is a multiple of 4, so it must contain either two regular items and one pairing item, or two pairing items and one filler item:
* If a 3-set contains two pairing items u<sub>ij</sub>, u<sub>kl</sub> and one filler item, then the sum of the two pairing items must be 44T+4 = 4*(5T+6T)+2+2, so they must have matching sizes (a<sub>i</sub>+a<sub>j</sub>=a<sub>k</sub>+a<sub>l</sub>). Therefore, by replacing as needed, we can assume that the two pairing items are in fact u<sub>ij</sub> and u<sub>ij</sub>'. Therefore, the remaining pairing items also consist of ''n'' matching pairs.
* Therefore, the remaining 3-sets can be partitioned into two groups: ''n'' 3-sets containing the items u<sub>ij</sub>, and ''n'' 3-sets containing the items u<sub>ij</sub>'. In each matching pair of 3-sets, the sum of the two pairing items u<sub>ij</sub>+u<sub>ij</sub>' is 44T+4, so the sum of the four regular items is 84T+4. Therefore, from the four regular items, we construct a 4-set in A, with sum T.
=== Reduction from 4-partition to 3-partition ===
| 