Source: EXACT COVER BY 3-SETS
Target: SUBSET PRODUCT
Motivation: This is the reference transformation from Garey & Johnson (attributed to Yao, 1978) proving that Subset Product is NP-complete in the strong sense. It uses a prime-number encoding to translate set coverage constraints into multiplicative constraints.
Reference: Garey & Johnson, Computers and Intractability, SP14, p.224
GJ Source Entry
[SP14] SUBSET PRODUCT
INSTANCE: Finite set A, a size s(a)∈Z^+ for each a∈A, and a positive integer B.
QUESTION: Is there a subset A'⊆A such that the product of the sizes of the elements in A' is exactly B?
Reference: [Yao, 1978b]. Transformation from X3C.
Comment: NP-complete in the strong sense.
Reduction Algorithm
Input: An X3C instance with universe U = {u_1, ..., u_{3q}} and a collection C = {C_1, ..., C_m} of 3-element subsets of U.
Output: A Subset Product instance with elements and a target product B.
Construction:
- Assign a distinct prime number p_i to each element u_i ∈ U. Use the first 3q primes: p_1 = 2, p_2 = 3, p_3 = 5, p_4 = 7, ...
- For each 3-element set C_j = {u_a, u_b, u_c} ∈ C, create an element with size s_j = p_a * p_b * p_c.
- Set the target product B = p_1 * p_2 * ... * p_{3q} (the product of all assigned primes).
Correctness:
- Forward: If C' ⊆ C is an exact cover (q sets covering U exactly), then the product of the corresponding sizes equals p_1 * p_2 * ... * p_{3q} = B, since each prime appears exactly once across the q selected sets.
- Backward: If a subset of sizes has product B, then by the fundamental theorem of arithmetic, the prime factorization must be exactly p_1 * p_2 * ... * p_{3q}. Since each s_j is a product of exactly 3 distinct primes from our set, the selected subset must cover each element exactly once, giving an exact cover.
Strong NP-completeness: The sizes s_j are products of at most 3 primes, each at most O(3q * log(3q)) by the prime number theorem. So all numbers in the instance are polynomially bounded in the input size, establishing strong NP-completeness.
Size Overhead
| Target metric (code name) |
Polynomial (using symbols above) |
num_elements |
num_sets (= m = |C|) |
target (magnitude) |
Product of first 3q primes ≈ e^(3q) (by prime number theorem) |
Validation Method
Forward direction: Given an exact cover C' = {C_{j1}, ..., C_{jq}}, take A' = {s_{j1}, ..., s_{jq}}. The product is s_{j1} * ... * s_{jq} = (p_{a1}*p_{b1}*p_{c1}) * ... * (p_{aq}*p_{bq}*p_{cq}). Since C' is an exact cover, each p_i appears exactly once, so the product equals p_1 * ... * p_{3q} = B.
Backward direction: Given A' with product B = p_1 * ... * p_{3q}, by unique prime factorization, the selected sizes must collectively contain each p_i exactly once. Since each size is a product of exactly 3 primes corresponding to the elements of a 3-set, the corresponding sets form an exact cover of U.
Example
X3C Instance:
- U = {u1, u2, u3, u4, u5, u6} (3q = 6, so q = 2)
- C = {C1={u1,u2,u3}, C2={u4,u5,u6}, C3={u1,u3,u5}, C4={u2,u4,u6}}
Prime assignment: p1=2, p2=3, p3=5, p4=7, p5=11, p6=13.
Subset Product instance:
- s1 = 235 = 30 (for C1)
- s2 = 71113 = 1001 (for C2)
- s3 = 2511 = 110 (for C3)
- s4 = 3713 = 273 (for C4)
- B = 235711*13 = 30030
Solution: A' = {s1, s2} = {30, 1001}, product = 30 * 1001 = 30030 = B. This corresponds to the exact cover {C1, C2}.
Alternative: A' = {s3, s4} = {110, 273}, product = 110 * 273 = 30030 = B. This corresponds to the exact cover {C3, C4}.
References
- [Yao, 1978b]: [
Yao1978b] Andrew C. Yao (1978). "private communication".
Source: EXACT COVER BY 3-SETS
Target: SUBSET PRODUCT
Motivation: This is the reference transformation from Garey & Johnson (attributed to Yao, 1978) proving that Subset Product is NP-complete in the strong sense. It uses a prime-number encoding to translate set coverage constraints into multiplicative constraints.
Reference: Garey & Johnson, Computers and Intractability, SP14, p.224
GJ Source Entry
Reduction Algorithm
Input: An X3C instance with universe U = {u_1, ..., u_{3q}} and a collection C = {C_1, ..., C_m} of 3-element subsets of U.
Output: A Subset Product instance with elements and a target product B.
Construction:
Correctness:
Strong NP-completeness: The sizes s_j are products of at most 3 primes, each at most O(3q * log(3q)) by the prime number theorem. So all numbers in the instance are polynomially bounded in the input size, establishing strong NP-completeness.
Size Overhead
num_elementsnum_sets(= m = |C|)target(magnitude)Validation Method
Forward direction: Given an exact cover C' = {C_{j1}, ..., C_{jq}}, take A' = {s_{j1}, ..., s_{jq}}. The product is s_{j1} * ... * s_{jq} = (p_{a1}*p_{b1}*p_{c1}) * ... * (p_{aq}*p_{bq}*p_{cq}). Since C' is an exact cover, each p_i appears exactly once, so the product equals p_1 * ... * p_{3q} = B.
Backward direction: Given A' with product B = p_1 * ... * p_{3q}, by unique prime factorization, the selected sizes must collectively contain each p_i exactly once. Since each size is a product of exactly 3 primes corresponding to the elements of a 3-set, the corresponding sets form an exact cover of U.
Example
X3C Instance:
Prime assignment: p1=2, p2=3, p3=5, p4=7, p5=11, p6=13.
Subset Product instance:
Solution: A' = {s1, s2} = {30, 1001}, product = 30 * 1001 = 30030 = B. This corresponds to the exact cover {C1, C2}.
Alternative: A' = {s3, s4} = {110, 273}, product = 110 * 273 = 30030 = B. This corresponds to the exact cover {C3, C4}.
References
Yao1978b] Andrew C. Yao (1978). "private communication".