[Model] SubsetSum

[isPANN]

Motivation

SUBSET SUM (P140) from Garey & Johnson, A3 SP13. One of Karp's original 21 NP-complete problems (1972). Given a set of positive integers and a target value B, the problem asks whether any subset sums to exactly B. PARTITION is the special case where B equals half the total sum. SUBSET SUM is a fundamental building block for cryptographic schemes (e.g., Merkle-Hellman knapsack) and serves as a source for many further reductions. Though NP-complete, it is solvable in pseudo-polynomial time O(nB) by dynamic programming.

Associated reduction rules:

• As target: R78 (PARTITION to SUBSET SUM)
• As source: R85 (SUBSET SUM to K-th LARGEST SUBSET), R101 (SUBSET SUM to CAPACITY ASSIGNMENT), R160 (SUBSET SUM to INTEGER KNAPSACK), R181 (SUBSET SUM to INTEGER EXPRESSION MEMBERSHIP)

Definition

Name: SubsetSum

Canonical name: Subset Sum
Reference: Garey & Johnson, Computers and Intractability, A3 SP13

Mathematical definition:

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?

Variables

• Count: n = |A| (one binary variable per element)
• Per-variable domain: {0, 1} -- 0 means element is not in A', 1 means element is in A'
• Meaning: x_i = 1 if element a_i is included in the selected subset A'. The problem is feasible iff Sum_{i: x_i=1} s(a_i) = B.

Schema (data type)

Type name: SubsetSum
Variants: none (sizes are plain positive integers)

Field	Type	Description
sizes	Vec<u64>	Positive integer size s(a) for each element a in A
target	u64	Target sum B

Complexity

• Best known exact algorithm: The Horowitz-Sahni meet-in-the-middle algorithm (1974) solves SUBSET SUM in O*(2^(n/2)) time and O*(2^(n/2)) space. Schroeppel and Shamir (1981) improved the space to O*(2^(n/4)) while maintaining the same O*(2^(n/2)) time bound. The O*(2^(n/2)) time complexity remains the best known worst-case bound for the general problem and is a major open question in exact algorithms. [Horowitz & Sahni, JACM 21(1):73-90, 1974; Schroeppel & Shamir, SIAM J. Comput. 10(3):456-464, 1981.]

Specialization

• PARTITION is the special case where B = (Sum s(a)) / 2.
• KNAPSACK generalizes SUBSET SUM by allowing separate weights and values and using an inequality constraint (Sum w(a) <= C) with an objective (maximize Sum v(a)).
• The 0-1 KNAPSACK problem with w_i = v_i for all items is equivalent to SUBSET SUM.
• Solvable in pseudo-polynomial time O(nB) by dynamic programming.

Extra Remark

Full book text:

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).

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^n subsets; check if any has sum exactly B.)
• It can be solved by reducing to integer programming. (Binary ILP with constraint Sum x_i * s(a_i) = B.)
• Other: Pseudo-polynomial DP in O(nB) time and O(B) space; meet-in-the-middle in O*(2^(n/2)) time.

Example Instance

Input:
A = {a_1, a_2, a_3, a_4, a_5, a_6} with sizes s = {3, 7, 1, 8, 2, 4} (n = 6 elements)
Target B = 11.

Feasible assignment:
A' = {a_1, a_4} = {3, 8} (sum = 3 + 8 = 11 = B)

Another solution: A' = {a_2, a_6} = {7, 4} (sum = 7 + 4 = 11 = B)

Answer: YES -- a subset summing to exactly B = 11 exists.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; many planned reduction connections (5 rules cited)
Non-trivial	⚠️ Warn	Closely related to existing Knapsack; distinct trait (SatisfactionProblem) but relationship needs discussion
Correctness	✅ Pass	All references verified; complexity bounds correct
Well-written	✅ Pass	Clean example, complete template, precise definition

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

SubsetSum does not exist in the codebase. The issue identifies 6 reduction connections (1 as target from PARTITION, 4 as source to various problems), making it a high-connectivity node in the reduction graph. The motivation is strong: fundamental NP-complete problem with applications in cryptography and as a building block for further reductions.

Result: Pass

Non-trivial

SubsetSum has a different trait implementation than the existing Knapsack model:

• Knapsack is an OptimizationProblem (maximize value subject to weight capacity, inequality constraint)
• SubsetSum is a SatisfactionProblem (does a subset sum to exactly B?, equality constraint)

The issue correctly notes: "The 0-1 KNAPSACK problem with w_i = v_i for all items is equivalent to SUBSET SUM." However, in the project's type system, SubsetSum implements SatisfactionProblem (Metric = bool) while Knapsack implements OptimizationProblem (Metric = SolutionSize). These are different traits with different solver APIs (find_satisfying vs find_best). The problems are mathematically related but structurally distinct in the codebase.

One concern: could SubsetSum be handled as a variant of Knapsack (e.g., by adding a satisfaction mode)? The project convention treats satisfaction and optimization problems as separate models, so a separate SubsetSum model is appropriate.

Result: Warn — pass as a distinct problem, but the relationship to Knapsack should be explicitly discussed in the implementation to avoid confusion.

Correctness

References verified:

• Horowitz and Sahni (1974), "Computing Partitions with Applications to the Knapsack Problem," JACM 21(2):277-292 — confirmed at https://dl.acm.org/doi/10.1145/321812.321823. The O*(2^(n/2)) meet-in-the-middle bound is correct.
• Schroeppel and Shamir (1981), "A T=O(2^(n/2)), S=O(2^(n/4)) Algorithm for Certain NP-Complete Problems," SIAM J. Comput. 10(3):456-464 — confirmed at https://epubs.siam.org/doi/10.1137/0210033. The space improvement to O*(2^(n/4)) is correct.
• The claim that SubsetSum is one of Karp's original 21 problems is essentially correct: Karp's "Knapsack" problem is closer to what is now called Subset Sum.
• The pseudo-polynomial time O(nB) dynamic programming bound is a standard textbook result.
• The GJ classification SP13 and the transformation from PARTITION are correctly stated.

Result: Pass

Well-written

Template completeness: All required sections are present and substantive.

Strengths:

• The example is clean and correct: sizes {3,7,1,8,2,4}, target B=11, two valid solutions given ({3,8} and {7,4}).
• The variable encoding is clear: n binary variables, one per element.
• The mathematical definition matches the GJ book text exactly.
• The schema is minimal and clean with just two fields (sizes, target).
• Multiple solver approaches are discussed (brute force, ILP, DP, meet-in-the-middle).

Minor observations (not failures):

• The schema uses u64 instead of a generic weight type. Since SubsetSum only has one "weight-like" parameter (sizes), using u64 is reasonable for this problem.
• The getter methods are not explicitly listed in the Schema section. Expected methods: num_items() (= n), target() (= B).

Result: Pass

Recommendations

• Explicitly document the relationship to the existing Knapsack model in the implementation, noting the different trait (SatisfactionProblem vs OptimizationProblem).
• Add getter method names to the schema section: num_items(), target().
• Consider whether a reduction from SubsetSum to Knapsack (or vice versa) should be one of the associated rules.