[Rule] PARTITION to SUBSET SUM

[isPANN]

Source: PARTITION
Target: SUBSET SUM
Motivation: Establishes NP-completeness of SUBSET SUM via polynomial-time reduction from PARTITION. This is a textbook-canonical reduction: PARTITION is the special case of SUBSET SUM where the target B equals half the total sum. The reduction is essentially an embedding -- the PARTITION instance is directly re-interpreted as a SUBSET SUM instance with B = S/2. Referenced in Karp (1972) and Garey & Johnson (1979, SP13).

Reference: Garey & Johnson, Computers and Intractability, SP13, p.223

GJ Source Entry

[SP13] SUBSET SUM
INSTANCE: Finite set A, size s(a) in Z^+ for each a in A, positive integer B.
QUESTION: Is there a subset A' <= A such that the sum of the sizes of the elements in A' is exactly B?
Reference: [Karp, 1972]. Transformation from PARTITION.
Comment: Solvable in pseudo-polynomial time (see Section 4.2).

Reduction Algorithm

Summary:

Given a PARTITION instance (finite set A with sizes s(a) in Z^+), construct a SUBSET SUM instance as follows:

1. Elements: Keep the same set A with the same sizes s(a). That is, the SUBSET SUM element set is identical to the PARTITION element set.
2. Target: Set B = S / 2, where S = Sum_{a in A} s(a) is the total sum of all element sizes. If S is odd, the PARTITION instance has no solution; in this case, return a trivially infeasible SUBSET SUM instance with sizes = [] and target = 1.
3. Correctness: PARTITION asks: "Is there A' <= A with Sum_{a in A'} s(a) = Sum_{a in A\A'} s(a)?" This is equivalent to asking "Is there A' <= A with Sum_{a in A'} s(a) = S/2?", which is exactly the SUBSET SUM question with target B = S/2. The reduction is a trivial embedding.
4. Solution extraction: The SUBSET SUM solution A' (the subset summing to B = S/2) is directly one side of the balanced partition. The other side is A \ A'.

Size Overhead

Symbols:

• n = |A| = num_elements of source PARTITION instance

Target metric (code name)	Polynomial (using symbols above)
num_elements	num_elements (= n)

Derivation: The SUBSET SUM instance has exactly the same n elements as the PARTITION instance. The target B is computed as S/2, a data parameter. Construction is O(n).

Validation Method

• Closed-loop test: reduce source PARTITION instance, solve target SUBSET SUM with BruteForce, extract solution, verify on source
• Compare with known results from literature
• Edge cases: test with odd total sum (no solution), test with all-equal elements (always solvable if n is even)

Example

Source instance (PARTITION):
A = {a_1, a_2, a_3, a_4, a_5, a_6, a_7} with sizes s = {5, 3, 8, 2, 7, 1, 4} (n = 7 elements)
Total sum S = 5 + 3 + 8 + 2 + 7 + 1 + 4 = 30
A balanced partition exists iff a subset summing to S/2 = 15 can be found.

Constructed SUBSET SUM instance:
Items: same 7 elements with sizes {5, 3, 8, 2, 7, 1, 4}
Target B = 15.

Solution:
Select A' = {a_1, a_3, a_4} = {5, 8, 2} (sum = 5 + 8 + 2 = 15 = B). YES.

Solution extraction:
Partition side 1: A' = {5, 8, 2} (sum = 15)
Partition side 2: A \ A' = {3, 7, 1, 4} (sum = 3 + 7 + 1 + 4 = 15)
Balanced partition confirmed.

Negative case:
A = {5, 3, 8, 2, 7, 1, 3} (n = 7 elements), total sum S = 29 (odd).
Since S is odd, the reduction returns a trivially infeasible SUBSET SUM instance: sizes = [], target = 1. No empty subset sums to 1, so the answer is NO. PARTITION has no solution because no balanced partition can exist when S is odd.

References

• [Karp, 1972]: [Karp1972] Richard M. Karp (1972). "Reducibility among combinatorial problems". In: Complexity of Computer Computations. Plenum Press.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from Partition to SubsetSum in the reduction graph
Non-trivial	⚠️ Warn	Very simple embedding (copies items, computes B = S/2), but does produce a distinct problem type with a new parameter
Correctness	✅ Pass	Karp (1972) and Garey & Johnson (1979, SP13) both verified in project bibliography
Well-written	❌ Fail	Wrong code metric names in overhead table; vague odd-sum handling

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

Pass. pred path Partition SubsetSum returns no path. This reduction adds a novel direct edge to the reduction graph, connecting Partition to the SubsetSum cluster (which further reduces to ClosestVectorProblem). Currently Partition only reduces to Knapsack, so this provides a second reduction target.

Non-trivial

Warn. The reduction is extremely simple — it copies the item set unchanged and computes B = S/2. The issue itself describes it as "a trivial embedding." However, it does not fall into the strict fail categories (variable substitution, subtype coercion, or same-problem identity): Partition and SubsetSum are distinct problem types with different schemas (Partition has only sizes, while SubsetSum has sizes + target), and the reduction does construct a new parameter. The concern is that there is essentially zero structural transformation, which makes it borderline.

Correctness

Pass. Both cited references are verified:

• Karp (1972) — "Reducibility among Combinatorial Problems" is entry karp1972 in docs/paper/references.bib. Partition is indeed problem feat: Implement integer programming solver for Coloring problem #20 in Karp's list.
• Garey & Johnson (1979) — "Computers and Intractability" is entry garey1979 in docs/paper/references.bib. SP13 correctly describes SUBSET SUM with the transformation from PARTITION noted in the original text.

The mathematical claim is correct: PARTITION asks whether a subset sums to S/2, which is exactly SUBSET SUM with target B = S/2.

Well-written

Fail. Several issues found:

1. Wrong code metric names in overhead table. The table uses num_items as the target metric, but pred show SubsetSum reports the actual size field as num_elements. Similarly, the source Partition also uses num_elements, not num_items. The overhead formula and symbol definitions must use the actual getter method names.

2. Vague odd-sum handling. The algorithm says "one can set B = floor(S/2) (the SUBSET SUM instance will have no solution either)" but this is incorrect — in the negative example, SubsetSum with target 14 does have a solution ({5, 3, 2, 1, 3} = 14), so setting B = floor(S/2) does NOT guarantee the SubsetSum instance has no solution. The reduction must explicitly handle odd S (e.g., return a trivially infeasible SubsetSum instance like sizes = [], target = 1), and the algorithm section should specify this precisely.

3. Negative example is misleading. The example claims "No subset sums to exactly 14.5, so PARTITION has no solution" — this is correct reasoning, but then says the SubsetSum instance with target 14 "might or might not have a solution" and that "that is irrelevant." In fact, it IS relevant because if the reduction sets B = 14, the SubsetSum solver would return YES (a subset summing to 14 exists), which would give a wrong answer for PARTITION. This demonstrates that the reduction algorithm itself is underspecified for the odd-sum case.

4. Symbol n used but num_elements is the actual code name. The Symbols section defines n = |A| = num_items — both the alias and the code name are wrong relative to the actual Partition/SubsetSum getter (num_elements).

Recommendations

• Fix the overhead table to use num_elements (the actual size field for both Partition and SubsetSum).
• Specify the exact handling for odd total sum in the reduction algorithm — e.g., "If S is odd, return SubsetSum with sizes = [] and target = 1 (trivially infeasible)."
• Fix the negative example to be consistent with the chosen odd-sum handling strategy.