[Rule] PARTITION to MINIMUM SUM OF SQUARES

[isPANN]

Source: Partition
Target: SumOfSquaresPartition
Motivation: Establishes NP-hardness of SumOfSquaresPartition from Partition (one of Karp's 21). The reduction is Garey & Johnson SP19's textbook construction restricted to K = 2: among all 2-way partitions of A, the sum of squared group sums is minimized when the two groups have equal sums (S/2 each), giving minimum S²/2. Hence Partition is YES iff the minimum sum of squares is ⌈S²/2⌉ (equivalently, ≤ S²/2 when S is even).
Reference: Garey & Johnson, Computers and Intractability, SP19, p. 225.

GJ Source Entry

[SP19] MINIMUM SUM OF SQUARES
INSTANCE: Finite set A, a size s(a) in Z^+ for each a in A, positive integers K<=|A| and J.
QUESTION: Can A be partitioned into K disjoint sets A_1,A_2,...,A_K such that
Sum_{i=1}^{K}(Sum_{a in A_i} s(a))^2 <= J ?
Reference: Transformation from PARTITION or 3-PARTITION.
Comment: NP-complete in the strong sense. NP-complete in the ordinary sense and solvable in pseudo-polynomial time for any fixed K. Variants in which the bound K on the number of sets is replaced by a bound B on either the maximum set cardinality or the maximum total set size are also NP-complete in the strong sense [Wong and Yao, 1976].

Codebase Note: Why This Is a Witness Reduction (No J Field)

The SumOfSquaresPartition model in this codebase is a pure minimization problem with Value = Min<i64> and fields (sizes, num_groups). There is no J bound field and no Decision<SumOfSquaresPartition> registered. So the reduction is implemented in the same witness-style form as partition_multiprocessorscheduling.rs:

• The target SumOfSquaresPartition instance encodes the construction (identical sizes, K = 2).
• ReductionResult::extract_solution is the identity (the group assignment is a valid Partition subset assignment).
• The closed-loop test relies on source.evaluate(extracted_config) — Partition::evaluate already returns Or(true) exactly when the config splits the sum in half. The bound J = S²/2 is therefore an implicit property of the optimal target witness, not a stored field.

This matches the precedent set by partition_multiprocessorscheduling.rs and other Partition → ... reductions where the target is constructed to make Partition's YES/NO answer recoverable from source.evaluate(extract_solution(target_witness)).

(A separate follow-up issue may introduce Decision<SumOfSquaresPartition> with an explicit J bound; this issue does not depend on that.)

Reduction Algorithm

Given a Partition instance with sizes A = {s_1, ..., s_n} (s_i > 0, source Value = Or), construct a SumOfSquaresPartition (Value = Min<i64>) as follows:

1. Guard small instances. If n < 2 (i.e. K = 2 > n would violate SumOfSquaresPartition's constructor invariant num_groups ≤ num_elements), emit a sentinel target SumOfSquaresPartition::new(vec![1, 1], 2) and remember source_n. extract_solution returns vec![0; source_n], on which Partition::evaluate returns Or(false) — the correct YES/NO answer because a single positive element cannot be split into two equal-sum groups (and Partition::new already rejects n = 0).
2. Normal case (n ≥ 2). Cast each s_i: u64 to i64 (sizes in Partition are bounded by u64::MAX; in practice all canonical examples and reductions in this repo use values well within i64::MAX). Construct target = SumOfSquaresPartition::new(sizes_i64, 2).
3. Witness extraction. extract_solution(target_config) = target_config.to_vec() when its length equals source_n; otherwise (sentinel case) vec![0; source_n].

Why this works (G&J SP19 specialized to K=2). Let S = Σ s_i and let S_1, S_2 be the two group sums under a 2-partition (S_1 + S_2 = S). Then
S_1² + S_2² = (S_1 + S_2)² − 2 S_1 S_2 = S² − 2 S_1 S_2,
which is minimized when S_1 S_2 is maximized, i.e. when S_1 = S_2 = S/2. The minimum is S²/2 (achievable iff S is even and a balanced subset exists).

So:

• Partition YES ⇔ some 2-partition of A has S_1 = S_2 ⇔ min Σ (group_sum)² = S²/2 ⇔ the target's optimal witness is a balanced split ⇔ Partition::evaluate(extracted_witness) = Or(true).
• Partition NO ⇔ every 2-partition has S_1 ≠ S_2 ⇔ target's optimum strictly exceeds S²/2 ⇔ the optimal witness is unbalanced ⇔ Partition::evaluate(extracted_witness) = Or(false).

This is the standard test pattern used by test_partition_to_multiprocessorscheduling_solution_extraction.

Size Overhead

Symbols:

• num_elements = |A| (getter on Partition).

Target metric (code name)	Polynomial expression
num_elements	num_elements
num_groups	2

(Field names match SumOfSquaresPartition's size_fields = ["num_elements", "num_groups"]. The macro overhead validator will reject any other name.)

Construction is O(n) time and O(n) space.

Validation Method

• Closed-loop test (balanced even-sum case). Input Partition::new(vec![3, 1, 1, 2, 2, 1]) (n=6, S=10). Expected: target optimal min = 50 = S²/2; Partition::evaluate(extracted_witness) = Or(true).
• Closed-loop test (odd-sum NO case). Input Partition::new(vec![2, 4, 5]) (n=3, S=11). Expected: target optimal min > 60.5 (in fact = 61 = 5² + 6² for split {5},{2,4}); Partition::evaluate(extracted_witness) = Or(false).
• Closed-loop test (even-sum but unbalanced NO case). Input Partition::new(vec![1, 1, 1, 5]) (n=4, S=8). No balanced subset (smallest gap is {5} vs {1,1,1} giving 5 vs 3). Expected: target min > 32; extracted witness fails Partition::evaluate.
• Singleton corner case. Input Partition::new(vec![5]) (n=1). Sentinel path triggers; extract_solution returns [0]; Partition::evaluate([0]) = Or(false).
• Structure tests. For each non-sentinel input, assert target.sizes() == source.sizes().map(i64::from), target.num_groups() == 2, target.num_elements() == source.num_elements().

Example

Source (Partition): A = {3, 1, 1, 2, 2, 1} (n = 6, S = 10).
A balanced partition requires each half to sum to S/2 = 5.

Constructed target (SumOfSquaresPartition):

• sizes = [3, 1, 1, 2, 2, 1] (as Vec<i64>),
• num_groups = 2.
• (No J field — the bound S²/2 = 50 is an implicit property of the optimum.)

Optimal target witness (one of several): [0, 1, 1, 0, 1, 1] → group 0 sums to 3+2 = 5, group 1 sums to 1+1+2+1 = 5. Target value: 5² + 5² = 50 = S²/2.

Source-side check: Partition::evaluate([0, 1, 1, 0, 1, 1]) = Or(5+5 == 10) = Or(true). ✓

Imbalanced comparison. Witness [0, 0, 0, 1, 0, 0] → groups {3,1,1,2,1} (sum 8) vs {2} (sum 2). Target value: 64 + 4 = 68 > 50. Source-side: Partition::evaluate([0,0,0,1,0,0]) = Or(2 ≠ 8) = Or(false). Confirms only balanced splits achieve the optimum.

Singleton sentinel. Partition::new(vec![5]) → sentinel target SumOfSquaresPartition::new(vec![1,1], 2). extract_solution(any) = [0] (length matches source_n = 1). Partition::evaluate([0]) = Or(false) — correct.

References

• Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, problem SP19, p. 225. W. H. Freeman.
• C. K. Wong and A. C. Yao (1976). "A combinatorial optimization problem related to data set allocation." Revue Française d'Automatique, Informatique, Recherche Opérationnelle, Sér. Bleue 10(suppl.), pp. 83–95.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from Partition to SumOfSquaresPartition
Non-trivial	❌ Fail	Reduction is a trivial embedding — Partition is a special case of SumOfSquaresPartition with K=2
Correctness	✅ Pass	Garey & Johnson SP19 reference verified; Wong and Yao (1976) confirmed real
Well-written	❌ Fail	Wrong target name, incorrect size field names, type mismatch

Overall: 2 passed, 0 warnings, 2 failed

---

Usefulness

Pass. No reduction path currently exists from Partition to SumOfSquaresPartition in the codebase. The Partition problem currently only reduces to Knapsack. Adding this connection would link Partition to SumOfSquaresPartition (and transitively to ILP via SumOfSquaresPartition's existing ILP reduction).

Note: The target problem already exists in the codebase as SumOfSquaresPartition, not "MINIMUM SUM OF SQUARES" or "MinimumSumOfSquares" as the issue states.

Non-trivial

Fail. This reduction is a trivial embedding of a special case into the general problem. The entire "reduction" consists of:

1. Keep the same items and sizes (identity copy)
2. Set K = 2
3. Compute a threshold J from the input

There is no gadget construction, no auxiliary variables, no structural transformation. Partition is literally the K=2 special case of SumOfSquaresPartition — the reduction is conceptually equivalent to saying "a Partition instance is a SumOfSquaresPartition instance with K=2." This falls squarely under the "same-problem identity" and "subtype coercion" categories in the non-triviality check: the mapping merely casts to a more general problem type with no structural change to the instance.

The solution extraction is equally trivial — the two groups from the SumOfSquaresPartition solution directly yield the two Partition subsets with no transformation needed.

Correctness

Pass. The mathematical claims are correct:

• Garey & Johnson SP19 (p. 225): Confirmed. "MINIMUM SUM OF SQUARES" is problem SP19 in Computers and Intractability. The GJ entry quoted in the issue matches the known problem definition. The stated reduction from PARTITION (or 3-PARTITION) is consistent with GJ's reference.
• Wong and Yao (1976): Verified. C. K. Wong and A. C. Yao, "A Combinatorial Optimization Problem Related to Data Set Allocation," Revue Française d'Automatique, Informatique, Recherche Opérationnelle 10(suppl.), pp. 83–95, 1976. The paper exists and addresses variants of this problem.
• Algebraic identity: The claim that S₁² + S₂² is minimized when S₁ = S₂ = S/2 is mathematically correct (follows from the AM-QM inequality or direct calculus).

Well-written

Fail. Several issues found:

1. Wrong target problem name: The issue calls the target "MINIMUM SUM OF SQUARES" throughout, but the problem already exists in the codebase as SumOfSquaresPartition. The issue should use the correct codebase name to avoid confusion during implementation. The Source/Target fields should read Partition and SumOfSquaresPartition.

2. Incorrect size field names in overhead table: The issue uses num_items and num_groups as the target metric code names, but the actual SumOfSquaresPartition problem has size fields num_elements and num_groups. The num_items field does not exist on SumOfSquaresPartition. (Verified via pred show SumOfSquaresPartition --json → size_fields: ["num_elements", "num_groups"].)

3. Type mismatch not addressed: Partition.sizes is Vec<u64> while SumOfSquaresPartition.sizes is Vec<i64>. The reduction algorithm does not mention this type conversion, which will require explicit handling in implementation (casting u64 to i64, with potential overflow considerations).

4. Missing threshold parameter: The issue describes setting J = S²/2, but the SumOfSquaresPartition schema has no J or threshold field — it is a minimization problem (minimize sum of squared group sums), not a decision problem with a bound. The reduction algorithm is written for the decision version from GJ, but the codebase model is the optimization version. The algorithm needs to be rewritten to account for this: the reduction should simply construct the SumOfSquaresPartition instance with K=2 and let the solver minimize; the Partition answer is YES iff the minimum equals S²/2.

5. Validation section is generic: The validation method says "compare with known results from literature" without specifying which results or how.

Recommendations

• Since SumOfSquaresPartition already exists, update all references to use the correct name.
• Fix the overhead table to use num_elements instead of num_items.
• Address the decision-vs-optimization mismatch: rewrite the algorithm for the optimization formulation used in the codebase.
• Consider whether this trivial embedding is worth a dedicated reduction rule, or whether it would be better handled as a natural variant edge or documented as a note in the SumOfSquaresPartition problem definition.

[isPANN]

Issue Quality Check — Rule (Re-check)

Re-checking after --force. Previous report stood at 2 passed / 2 failed; this re-check finds the issue body unchanged, adds the mandatory Completeness check (Rule Check 5), and updates the verdict accordingly.

Check	Result	Details
Usefulness	Pass	No existing path from Partition to SumOfSquaresPartition
Non-trivial	Fail	Identity-copy embedding of K=2 special case into the general K-group model
Correctness	Pass	G&J SP19 (p.225) and Wong & Yao (1976) both verified; G&J explicitly cites "Transformation from PARTITION or 3-PARTITION"
Completeness	Fail	Algorithm targets the G&J decision version with bound J, but the codebase model SumOfSquaresPartition is a pure minimization problem with no bound field; corner cases n=1 (K=2 >
Well-written	Fail	Wrong target name, wrong size-field name, no u64→i64 conversion, no acknowledgement of decision-vs-optimization mismatch

Overall: 2 passed, 0 warnings, 3 failed

---

Usefulness

Pass. pred path Partition SumOfSquaresPartition returns no path, so this reduction would be a new connection in the graph. Partition currently reduces out to SubsetSum, Knapsack, BinPacking, MultiprocessorScheduling, OpenShopScheduling, SequencingToMinimizeTardyTaskWeight, CosineProductIntegration, and ProductionPlanning. SumOfSquaresPartition only reduces forward to ILP and has no incoming reductions, so this link does pull a new node into the connected component.

Non-trivial

Fail. The construction is a subtype coercion: keep the same n items with the same sizes, set K = 2, derive a numeric threshold from the input. There is no gadget, no auxiliary variable, no structural transformation — Partition is literally the K=2 decision case of SumOfSquaresPartition, and solution extraction is the identity map (group 0 → subset A, group 1 → subset B). This falls under "same-problem identity / subtype coercion" in the Non-triviality criteria.

If the goal is to expose this connection in the reduction graph, it is more natural to (a) document it inside SumOfSquaresPartition as a witness embedding without filing it as a dedicated [Rule], or (b) reduce from Partition to an intermediate that does meaningful structural work.

Correctness

Pass. The cited claims are accurate:

• Garey & Johnson SP19 (p. 225): Verified. The G&J entry quoted in the issue body matches the published MINIMUM SUM OF SQUARES problem and explicitly lists "Transformation from PARTITION or 3-PARTITION", so the reduction direction (Partition → SP19) is in fact pointed to by the textbook.
• Wong & Yao (1976): Verified. C. K. Wong and A. C. Yao, "A Combinatorial Optimization Problem Related to Data Set Allocation," RAIRO Sér. Bleue 10(suppl.), pp. 83–95, 1976. The paper exists and addresses related variants (cardinality and total-size-bounded partitions, exponent α > 1 generalization).
• Algebraic identity min (S_1^2 + S_2^2) = S^2 / 2 at S_1 = S_2 = S/2: correct (follows from S_1^2 + S_2^2 = (S_1+S_2)^2 - 2 S_1 S_2 and AM-GM on S_1 S_2).

So the mathematics of the reduction is sound, even though it is not a polynomial-time Karp reduction into the model that actually lives in the codebase (see Completeness).

Completeness

Fail. This is the most important finding of the re-check. The cited theorem covers all PARTITION instances, but the construction the issue writes down does not survive contact with the codebase model for two distinct reasons, plus a hidden precondition on n.

Literature evidence. G&J SP19 (p. 225) states the target problem as a decision problem with an explicit bound J:

"QUESTION: Can A be partitioned into K disjoint sets A_1,...,A_K such that Sum_{i=1}^K (Sum_{a in A_i} s(a))^2 ≤ J ?"

The standard Partition → SP19 reduction (which the issue restates correctly) sets K = 2 and J = ⌊S²/2⌋ and answers YES iff a balanced partition exists. G&J's reduction is therefore a Karp reduction between decision problems.

Codebase corner-case research (pred show SumOfSquaresPartition --json). In this codebase, SumOfSquaresPartition is registered as a pure minimization problem with Value = Min<i64> and only two schema fields: sizes: Vec<i64> and num_groups: usize. There is no J, no bound, and no Decision<SumOfSquaresPartition> registered (pred show "Decision<SumOfSquaresPartition>" returns "Unknown problem"). As a result:

1. Decision-vs-optimization mismatch (substantive). The reduction as written needs a target with a threshold J to compare against. The codebase model does not have one. To match the issue's algorithm, the target would have to be Decision<SumOfSquaresPartition>, which is not in the registry. Without that, the only honest implementation is either:

   • an aggregate-only reduction that solves the minimization and compares the result to S²/2 outside the reduction itself (then it is no longer the construction the issue describes), or
   • first add Decision<SumOfSquaresPartition> via register_decision_variant! and target that. The issue body must spell this out.

2. Corner case n = 1 breaks the construction (substantive). Partition accepts any non-empty positive-integer vector — Partition::new(vec![5]) is a legitimate source instance (and the answer is NO since the only partition is {5}, ∅ with sums 5 and 0). The issue's algorithm sets K = 2 unconditionally. But SumOfSquaresPartition::try_new requires num_groups ≤ sizes.len() and panics otherwise. Tracing the algorithm on Partition([5]):

   • Step 1: copy items, sizes = [5].
   • Step 2: K = 2.
   • Step 3: J = ⌊25/2⌋ = 12.
   • Constructing the target: SumOfSquaresPartition::new(vec![5], 2) fails validation ("Number of groups must not exceed number of elements"). The reduction crashes.

   The issue body does not mention this case at all. Fix: special-case n = 1 (the source is trivially NO; emit any trivially-infeasible target), or restrict the source to n ≥ 2 and state that restriction explicitly.

3. Corner case "odd S" is acknowledged but the cure is wrong (substantive). The issue says "If S is odd, S²/2 is not an integer; set J = floor(S²/2) and the answer is NO since a balanced partition is impossible." With K = 2 and integer sizes, the minimum value of S_1² + S_2² over integer-valued partitions of an odd S is ((S-1)/2)² + ((S+1)/2)² = (S²+1)/2 = ⌈S²/2⌉ = ⌊S²/2⌋ + 1 > J. So the answer is correctly NO. But this only works in the decision formulation. In the codebase's minimization formulation, the reduction must still produce a well-formed target; comparing min ≤ J happens at the aggregate-extraction layer, not inside reduce_to. The issue is silent on how this aggregate comparison is wired (witness vs aggregate edge, threshold storage, etc.).

4. Corner case "duplicate sizes" works (trace: Partition([1,1,1,1]), S=4, J=8, K=2; balanced partition {1,1},{1,1} gives 4+4=8 ≤ J, YES). No issue here, just confirming the construction is correct when n ≥ K.

5. Corner case "single very large element" breaks balance (trace: Partition([10,1,1,1,1,1,1,1,1,1]), S=19, J=⌊361/2⌋=180; best split is {10},{1×9} with 100+81=181 > 180; NO, matching the fact that {10} cannot be balanced against any subset summing to 9.5).

Codebase precedent. The existing partition_subsetsum.rs rule explicitly handles the odd-sum corner case by returning a "trivially infeasible" target (SubsetSum::new_unchecked(vec![], BigUint::from(1u32))) and threads source_n through extract_solution so the source-side config has the right length. The issue gives no equivalent contingency, and SumOfSquaresPartition does not even support an "empty items" target (num_groups > sizes.len() panics, and K=0 panics).

Verdict. The cited theorem covers all PARTITION instances, but the construction as written ignores a precondition imposed by the target model (K ≤ n) and ignores the decision-vs-optimization mismatch between G&J's SP19 and this codebase's SumOfSquaresPartition. Per the Check 5 verdict table, "Traced corner case breaks the algorithm" → Fail (Incomplete).

Well-written

Fail. The previous review flagged several mechanical errors; they are still present in the issue body.

1. Wrong target problem name. The issue calls the target "MINIMUM SUM OF SQUARES" throughout. The codebase model is SumOfSquaresPartition (verified via pred show SumOfSquaresPartition). Source/Target labels and all narrative references must use SumOfSquaresPartition.

2. Wrong size-field name in the overhead table. The table uses num_items. The actual size_fields from pred show SumOfSquaresPartition --json are ["num_elements", "num_groups"]. The compile-time overhead validator will reject num_items because there is no num_items() getter on SumOfSquaresPartition. Replace num_items with num_elements.

3. Sizes type mismatch unaddressed. Partition.sizes is Vec<u64>; SumOfSquaresPartition.sizes is Vec<i64>. The reduction must cast each size; for inputs that exceed i64::MAX the cast must be guarded (in practice the existing Partition::new admits values up to u64::MAX). The issue body does not mention this.

4. Decision-vs-optimization mismatch not addressed in the text (also flagged under Completeness, but mechanically: the algorithm refers to J as a parameter of the target instance — there is no such field on SumOfSquaresPartition). The Reduction Algorithm should either (a) target Decision<SumOfSquaresPartition> and state that it must be added first, or (b) reframe the reduction as aggregate-only with the J comparison happening in the aggregate extractor.

5. Validation Method is generic. "Compare with known results from literature" gives the implementer nothing concrete. Spell out the closed-loop test instances (balanced n=4, odd-sum n=3, single-element n=1) and what each should return.

6. Example only exercises the happy path. The worked example uses sizes = [3,1,1,2,2,1] (S even, n large enough). Add at least one corner-case mini-example (odd S, or n=1) to show the algorithm's behavior on degenerate inputs.

Recommendations

• Drop this as a standalone [Rule] issue; the construction is a textbook embedding and the codebase already exposes the K=2 case implicitly. If the goal is to register the connection, file a [Model] issue for Decision<SumOfSquaresPartition> first, then revisit.
• If kept, rewrite Source/Target to Partition and SumOfSquaresPartition, switch overhead to num_elements / num_groups, and add explicit handling for n = 1 (and any other case where K > n).
• Consider whether Partition → Decision<SumOfSquaresPartition> belongs in the library at all once Partition → SubsetSum already exists: G&J's standard chain is PARTITION → SP19, but in this codebase Partition → SubsetSum → ... already covers the strong-NP-hardness story.

[isPANN]

auto-pipeline: parked on OnHold — SP19 reduction is identity-copy K=2 embedding (Partition is the K=2 special case of SumOfSquaresPartition); fails Non-trivial check regardless of body rewrite. Human triage needed.

[isPANN]

Issue Quality Check — Rule (Re-check, --force)

Re-running on the unchanged issue body. Previous re-check (2026-05-25) already returned 2 passed / 3 failed with Trivial, PoorWritten, and Incomplete labels applied. This pass confirms the same verdict with explicit literature evidence and corner-case traces for Rule Check 5.

Check	Result	Details
Usefulness	Pass	No existing path Partition → SumOfSquaresPartition (pred path returns "No reduction path")
Non-trivial	Fail	Identity-copy embedding: Partition is literally the K=2 decision instance of SumOfSquaresPartition
Correctness	Pass	G&J SP19 (p. 225) and Wong & Yao (1976) both verified; algebraic identity min(S_1^2 + S_2^2) = S^2/2 is correct
Completeness	Fail	Hidden precondition K ≤ n is violated for n=1; decision/optimization mismatch — codebase target has no bound field J
Well-written	Fail	Wrong target name throughout; size-field name num_items does not exist on target; u64→i64 cast unaddressed; no J field on target

Overall: 2 passed, 0 warnings, 3 failed

---

Usefulness

Pass. pred path Partition SumOfSquaresPartition returns no path. Partition currently reduces out to SubsetSum, Knapsack, BinPacking, MultiprocessorScheduling, OpenShopScheduling, SequencingToMinimizeTardyTaskWeight, IntegralFlowWithMultipliers, CosineProductIntegration, ProductionPlanning. SumOfSquaresPartition has zero incoming reductions and only reduces forward to ILP. So the proposed edge does add a new connection.

Non-trivial

Fail. The construction is a subtype coercion: keep the same n items with the same sizes, set K = 2, derive a numeric threshold J from the input. There is no gadget, no auxiliary variable, no structural transformation. Partition is the K=2 decision case of SumOfSquaresPartition, and solution extraction is the identity. This falls under "same-problem identity / subtype coercion" in the Non-triviality criteria.

Correctness

Pass.

• Garey & Johnson SP19 (p. 225): Verified. The quoted entry matches MINIMUM SUM OF SQUARES. The note Reference: Transformation from PARTITION or 3-PARTITION explicitly names this reduction direction.
• Wong & Yao (1976): Verified. C. K. Wong and A. C. Yao, A combinatorial optimization problem related to data set allocation, RAIRO Sér. Bleue 10(suppl.), pp. 83–95.
• Algebraic identity: S_1^2 + S_2^2 = (S_1+S_2)^2 - 2 S_1 S_2 = S^2 - 2 S_1 S_2, maximized at S_1 S_2 = S^2/4 (i.e. S_1 = S_2 = S/2), so min(S_1^2 + S_2^2) = S^2/2. Correct.

Completeness

Fail. This is the most important finding.

Cited theorem text (G&J SP19, p. 225):

"INSTANCE: Finite set A, a size s(a) in Z^+ for each a in A, positive integers K ≤ |A| and J.
QUESTION: Can A be partitioned into K disjoint sets A_1,A_2,...,A_K such that ∑_{i=1}^{K} (∑_{a ∈ A_i} s(a))^2 ≤ J ?
Reference: Transformation from PARTITION or 3-PARTITION."

Two things follow from this text:

1. The G&J target is a decision problem with an explicit bound J and an explicit instance-level precondition K ≤ |A|.
2. The standard PARTITION → SP19 reduction sets K = 2 and J = ⌊S²/2⌋.

Codebase target (pred show SumOfSquaresPartition --json):

"schema": { "fields": [
   {"name":"sizes","type_name":"Vec<i64>"},
   {"name":"num_groups","type_name":"usize"}] },
"size_fields": ["num_elements","num_groups"]

SumOfSquaresPartition is a pure minimization problem (Value = Min<i64>) with no J/bound field and no registered Decision<SumOfSquaresPartition> (verified: pred show "Decision<SumOfSquaresPartition>" returns "Unknown problem"). The source code at src/models/misc/sum_of_squares_partition.rs:62-74 enforces num_groups ≤ sizes.len() at construction time (Self::validate_inputs returns "Number of groups must not exceed number of elements" otherwise).

Hand-traced corner cases (≥2, non-canonical):

1. Partition([5]) (n = 1, S = 5, source answer = NO since the only partition is {5} vs ∅).

   • Step 1: copy items → sizes = [5].
   • Step 2: K = 2.
   • Step 3: J = ⌊25/2⌋ = 12.
   • Construct target: SumOfSquaresPartition::new(vec![5], 2) — panics because num_groups (2) > sizes.len() (1).
   • The reduction crashes on a legitimate source instance. The issue body never mentions this case. Algorithm broken.

2. Partition([1, 2]) (n = 2, S = 3, odd; source answer = NO).

   • Step 1: copy items → sizes = [1, 2].
   • Step 2: K = 2.
   • Step 3: J = ⌊9/2⌋ = 4.
   • Construct target: SumOfSquaresPartition::new(vec![1, 2], 2) — succeeds.
   • But the codebase target has no J field: there is nowhere to store the bound. The reduction either has to discard J (then it's not the reduction the issue describes), or target Decision<SumOfSquaresPartition> (which doesn't exist in the registry). The issue's algorithm cannot be implemented as written.

3. Partition([1, 1, 1, 1]) (n=4, S=4, even, balanced exists). Trace succeeds: SumOfSquaresPartition::new(vec![1,1,1,1], 2) is valid, and the minimum sum-of-squares is 2² + 2² = 8 = S²/2. But again the bound J = 8 has no field to live in.

Precedent in the codebase. src/rules/partition_subsetsum.rs handles the odd-sum corner case by returning a trivially-infeasible SubsetSum::new_unchecked(vec![], BigUint::from(1u32)) and threads source_n through extract_solution. The issue under review gives no equivalent contingency, and the target model does not even allow an empty-items construction.

Verdict (per Check 5 table).

Finding	Severity
Cited theorem's `K ≤	A
Cited theorem is a decision problem with bound J; codebase target has no J field and no registered Decision<...> wrapper	substantive
Body never explains how J is wired into the codebase model	substantive

Per "Traced corner case breaks the algorithm" → Fail (Incomplete).

Well-written

Fail. Mechanical issues from the previous review are still present.

1. Wrong target name. Issue says "MINIMUM SUM OF SQUARES" / "MinimumSumOfSquares"; codebase model is SumOfSquaresPartition (pred show MinimumSumOfSquares → "Unknown problem").

2. Wrong size-field name in overhead table. Table uses num_items; actual fields are ["num_elements", "num_groups"]. The compile-time overhead validator will reject num_items because there is no getter of that name on SumOfSquaresPartition.

3. Type mismatch unaddressed. Partition.sizes: Vec<u64> vs SumOfSquaresPartition.sizes: Vec<i64>. Inputs near u64::MAX cannot be cast losslessly; this needs an explicit handling note.

4. No J field on target. The Reduction Algorithm references J as a parameter of the target instance, but no such field exists. Either target Decision<SumOfSquaresPartition> (and state in the issue that it must be added first) or reframe the reduction as aggregate-only with the J comparison happening in the aggregate extractor.

5. Validation Method generic. "Compare with known results from literature" tells the implementer nothing. Spell out specific closed-loop test instances (balanced n=4, odd-sum n=3, single-element n=1).

6. Example only exercises the happy path. sizes = [3,1,1,2,2,1] (S even, n ≥ 2). Add at least one corner case (odd S, n=1).

Recommendations

• Drop this as a standalone [Rule] issue. The construction is a textbook embedding that the codebase already covers transitively via Partition → SubsetSum → .... G&J's SP19 chain is already represented in spirit by the strong-NP-hardness of SubsetSum/Knapsack.
• If kept, file a companion [Model] issue first for Decision<SumOfSquaresPartition> (via register_decision_variant!); then this rule becomes Partition → Decision<SumOfSquaresPartition> and can carry J properly.
• Add explicit handling for n = 1 (and any case where K > n), e.g. produce a trivially-infeasible target as in partition_subsetsum.rs.
• Fix Source/Target labels to Partition / SumOfSquaresPartition, and switch overhead table to num_elements / num_groups.

---

Compared with previous re-check (2026-05-25): same verdict (3 fails), evidence strengthened with explicit K ≤ n precondition trace from G&J SP19 quote and confirmed source-level panic at src/models/misc/sum_of_squares_partition.rs:62-74.