[Rule] SUBSET SUM to PARTITION

[zazabap]

Source: SubsetSum
Target: Partition
Motivation: SubsetSum is reachable from 3-SAT at 1 hop (via KSatisfiability → SubsetSum). Partition currently has 0 incoming reductions and is a gateway to 7 downstream problems (Knapsack, MultiprocessorScheduling, BinPacking, SequencingWithinIntervals, ShortestWeightConstrainedPath, CosineProductIntegration, SubsetSum). Adding this single reduction would make Partition and all its descendants reachable from 3-SAT, increasing the NP-hardness-verified count from 29 to potentially 35+.
Reference: Garey & Johnson, Computers and Intractability, SP12–SP13; Sipser, Introduction to the Theory of Computation, Chapter 7.

GJ Source Entry

[SP12] PARTITION
INSTANCE: Finite set A and a size s(a) ∈ Z⁺ for each a ∈ A.
QUESTION: Is there a subset A' ⊆ A such that Σ_{a ∈ A'} s(a) = Σ_{a ∈ A−A'} s(a)?
Reference: [Karp, 1972].

[SP13] SUBSET SUM
INSTANCE: Finite set A, size s(a) ∈ Z⁺ for each a ∈ A, and positive integer B.
QUESTION: Is there a subset A' ⊆ A such that Σ_{a ∈ A'} s(a) = B?
Reference: [Karp, 1972]. Transformation from PARTITION.

Reduction Algorithm

Given a SubsetSum instance with elements S = {s₁, …, sₙ} and target T:

1. Compute sum: Σ = Σᵢ sᵢ.
2. Compute padding element: d = |Σ − 2T|.
3. Construct Partition instance:
   • If d = 0 (i.e., Σ = 2T): output Partition(S) — no padding needed.
   • If d > 0: output Partition(S ∪ {d}), appending d as the (n+1)-th element.
4. Type conversion: SubsetSum uses BigUint sizes; Partition uses u64. Convert each element via to_u64() (valid for instances within u64 range).

Correctness:

Let Σ' = sum of the Partition instance.

Case d = 0 (Σ = 2T): The Partition instance is S with Σ' = 2T. Half = T. A subset summing to T exists ⟺ a balanced partition exists. ✓

Case Σ > 2T (d = Σ − 2T > 0): Σ' = Σ + (Σ − 2T) = 2(Σ − T). Half = Σ − T.

• Forward: If subset A ⊆ S sums to T, place A ∪ {d} on one side (sum = T + Σ − 2T = Σ − T = half) and S \ A on the other (sum = Σ − T = half). ✓
• Backward: Given a balanced partition, the padding element d is on one side. The S-elements on that side sum to (Σ − T) − d = (Σ − T) − (Σ − 2T) = T. ✓

Case Σ < 2T (d = 2T − Σ > 0): Σ' = Σ + (2T − Σ) = 2T. Half = T.

• Forward: If subset A ⊆ S sums to T, place A on one side (sum = T = half) and (S \ A) ∪ {d} on the other (sum = (Σ − T) + (2T − Σ) = T = half). ✓
• Backward: Given a balanced partition, the side without d has S-elements summing to T. ✓

Infeasible case (T > Σ): No subset can sum to T. Here d = 2T − Σ > Σ, so the Partition instance has one element larger than half the total sum (d > Σ'/2 = T), making it infeasible. ✓

Solution extraction:

• If d = 0: return config[0..n] directly (either side's assignment works since both sides sum to T).
• If Σ > 2T: the S-elements on the same side as the padding element form the subset summing to T.
• If Σ < 2T: the S-elements on the opposite side from the padding element form the subset summing to T.

Size Overhead

Target metric	Expression
num_elements	num_elements + 1

(Worst case adds one padding element. When Σ = 2T, no element is added.)

Validation Method

• Closed-loop test: construct a SubsetSum instance, reduce to Partition, solve Partition via BruteForce, extract SubsetSum solution, verify the extracted subset sums to T
• Test with Σ > 2T case (padding element on T-sum side)
• Test with Σ < 2T case (padding element on complement side)
• Test with Σ = 2T case (no padding element)
• Test infeasible instance (T > Σ or no subset sums to T)
• Test single-element instance

Example

Source instance (SubsetSum):
S = {1, 5, 6, 8}, T = 11, Σ = 20.

Σ < 2T (20 < 22), so d = 2T − Σ = 2.

Constructed Partition instance:
S' = {1, 5, 6, 8, 2}, Σ' = 22, half = 11.

Solution mapping:

• SubsetSum subset {5, 6} sums to 11 = T. ✓
• Partition config [1, 0, 0, 1, 1]: side 1 = {1, 8, 2} = 11, side 0 = {5, 6} = 11. ✓
• Padding element (index 4) is on side 1. Since Σ < 2T, the T-sum subset is on the opposite side (side 0): elements {5, 6}.
• Extract source config: [0, 1, 1, 0] where 1 means "in subset." Subset = {5, 6} = 11 = T. ✓

Infeasible example:
S = {3, 7, 11}, T = 5, Σ = 21. No subset sums to 5.
d = |21 − 10| = 11. S' = {3, 7, 11, 11}, Σ' = 32, half = 16.
No partition of {3, 7, 11, 11} into two sets of sum 16 exists. ✓

References

• Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Problems SP12 (Partition) and SP13 (Subset Sum).
• Karp, R. M. (1972). "Reducibility among combinatorial problems." In Complexity of Computer Computations, pp. 85–103.