[Model] Partition

[isPANN]

Motivation

PARTITION (P139) from Garey & Johnson, A3 SP12. A classical NP-complete problem useful for reductions to KNAPSACK, MULTIPROCESSOR SCHEDULING, SEQUENCING WITHIN INTERVALS, and many other problems. Though NP-complete, PARTITION is only weakly NP-hard: it admits a pseudo-polynomial dynamic-programming algorithm running in O(n · B_total) time, making it tractable when element sizes are small.

Definition

Name: Partition
Reference: Garey & Johnson, Computers and Intractability, A3 SP12

Mathematical definition:

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

Variables

• Count: n = |A| (one binary variable per element)
• Per-variable domain: {0, 1} — 0 means element goes to the first part, 1 means it goes to the second part
• Meaning: x_i = 0 if a_i ∈ A', x_i = 1 if a_i ∈ A \ A'. The problem is feasible iff Σ_{i: x_i=0} s(a_i) = Σ_{i: x_i=1} s(a_i) = B_total / 2.

Schema (data type)

Type name: Partition
Variants: none (no type parameters; sizes are plain positive integers)

Field	Type	Description
sizes	Vec<u64>	Positive integer size s(a) for each element a ∈ A

Complexity

• Best known exact algorithm: The Schroeppel–Shamir meet-in-the-middle algorithm (1981) solves PARTITION (via SUBSET SUM) in time O*(2^(n/2)) and space O*(2^(n/4)). The naive brute-force approach is O(2^n). [Schroeppel & Shamir, SIAM J. Comput. 10(4):456–464, 1981.]

Extra Remark

Full book text:

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]. Transformation from 3DM (see Section 3.1.5).
Comment: Remains NP-complete even if we require that |A'| = |A|/2, or if the elements in A are ordered as a_1,a_2,…,a_{2n} and we require that A' contain exactly one of a_{2i−1},a_{2i} for 1 ≤ i ≤ n. However, all these problems can be solved in pseudo-polynomial time by dynamic programming (see Section 4.2).

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^n subsets; check if any half sums to B_total / 2.)
• It can be solved by reducing to integer programming. (Binary ILP with constraint Σ x_i · s(a_i) = B_total / 2.)
• Other: Pseudo-polynomial DP in O(n · B_total) time and O(B_total) space (standard subset-sum DP table).

Example Instance

Input:
A = {3, 1, 1, 2, 2, 1} (n = 6 elements)
s(a_1) = 3, s(a_2) = 1, s(a_3) = 1, s(a_4) = 2, s(a_5) = 2, s(a_6) = 1
Total sum = 10; target half-sum = 5.

Feasible assignment:
A' = {a_1, a_4} = {3, 2} (sum = 5)
A \ A' = {a_2, a_3, a_5, a_6} = {1, 1, 2, 1} (sum = 5)

Answer: YES — a balanced partition exists.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in reduction graph; classic Karp #20 / GJ SP2
Non-trivial	✅ Pass	Distinct feasibility constraints from Knapsack and all other existing problems
Correctness	✅ Pass	Schroeppel--Shamir 1981 reference verified; O*(2^(n/2)) bound confirmed
Well-written	⚠️ Warn	Minor issues with motivation specificity and planned graph connectivity

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

Partition does not exist in the codebase (pred show Partition fails). It is one of Karp's 21 NP-complete problems (#20) and Garey & Johnson SP2. It is a foundational decision problem in the "Sets and Partitions" category. As a classic NP-complete problem, it serves as a natural source or target for multiple reduction rules (e.g., Partition to BinPacking is a known reduction already listed in the project's references.md).

Non-trivial

Partition is genuinely distinct from all 24 existing problems. The closest existing problem is Knapsack, but:

• Knapsack is an optimization problem (maximize value subject to a capacity constraint) with separate weights and values vectors.
• Partition is a satisfaction/decision problem (does an equal-sum bipartition exist?) with only a sizes vector and no capacity parameter.

The feasibility constraint (equal-sum split) and the absence of an optimization objective make this a structurally different problem that cannot be represented as a variant of Knapsack.

Correctness

Schroeppel & Shamir (1981): Verified. The paper "A T=O(2^{n/2}), S=O(2^{n/4}) Algorithm for Certain NP-Complete Problems" was published in SIAM Journal on Computing, Volume 10, Issue 3, pages 456--464, 1981. The O*(2^(n/2)) time bound for Subset Sum (and hence Partition) is correct.

Garey & Johnson, SP12: Correct classification. Partition is listed as problem [SP12] in Appendix A of "Computers and Intractability" (1979), under Sets and Partitions.

Karp (1972): The issue correctly notes that Partition is among Karp's 21 NP-complete problems, with the original reduction from 3DM via Exact Cover -> Knapsack -> Partition.

Weak NP-hardness claim: Correct. Partition admits a pseudo-polynomial O(n * B_total) dynamic programming algorithm, making it only weakly NP-hard.

Well-written

Strengths:

• Definition matches the canonical GJ formulation exactly.
• Variables section is clear with proper binary encoding.
• Schema is simple and appropriate (Vec<u64> for positive integer sizes).
• Example is non-trivial (6 elements), hand-verifiable, and fully worked.
• Both brute-force and ILP solver paths are identified.

Minor issues (warnings, not failures):

• Motivation could be more specific about planned reductions. The motivation mentions connections to "KNAPSACK, MULTIPROCESSOR SCHEDULING, SEQUENCING WITHIN INTERVALS" but does not specify which concrete reduction rules would be implemented to connect Partition to the existing reduction graph. Without at least one planned rule, the node would be an orphan. Consider mentioning at least one planned reduction (e.g., Partition -> BinPacking from GJ, or SubsetSum -> Partition).
• AI-generated warnings on Variables, Schema, Complexity, and Example sections are noted. These are informational and the content itself checks out, but the contributor should verify and remove the warnings before implementation.

Recommendations

• Add a concrete planned reduction rule to the issue body (e.g., "Planned rules: Partition -> BinPacking (GJ Section 3.1)") to ensure graph connectivity.
• The Horowitz-Sahni (1974) meet-in-the-middle algorithm (already in the project bibliography as horowitz1974) achieves the same O*(2^(n/2)) time bound and may be a simpler reference for implementation, since it does not require the space-optimized priority queue of Schroeppel-Shamir.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct from Knapsack — decision problem with equal-partition feasibility constraint
Correctness	✅ Pass	Schroeppel–Shamir reference verified; complexity bound correct
Well-written	⚠️ Warn	Minor issues: missing num_elements getter naming convention, satisfaction vs optimization trait unclear

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

Partition does not exist in the codebase (pred show Partition returns unknown). It is problem SP2 in Garey & Johnson and #20 in Karp's 21 NP-complete problems. It is a natural reduction target from Knapsack (already in the codebase) and a natural source for reductions to BinPacking (also in the codebase). The Karp reduction tree shows Knapsack → Partition, and Garey & Johnson document Partition → Bin Packing. Adding this problem connects existing nodes in the reduction graph.

The motivation section is well-written and explains the problem's role clearly.

Non-trivial

Partition is a satisfaction (decision) problem with the feasibility constraint that a subset must sum to exactly half the total. This is fundamentally different from:

• Knapsack (optimization: maximize value subject to capacity constraint — different objective and different constraint structure)
• SubsetSum (not in the codebase)

The equal-partition constraint is structurally distinct from any existing problem. This is a genuinely new problem.

Correctness

Schroeppel & Shamir (1981): Verified. "A T = O(2^{n/2}), S = O(2^{n/4}) Algorithm for Certain NP-Complete Problems," SIAM Journal on Computing, Vol. 10, No. 3, pp. 456–464, 1981. The issue cites "10(4):456–464" — the volume is correct (10) but the issue number should be 3, not 4. The page range 456–464 is correct. This is a very minor bibliographic error.

Note: The Horowitz & Sahni (1974) paper "Computing Partitions with Applications to the Knapsack Problem" is already in the project bibliography (horowitz1974). That earlier paper achieves O*(2^{n/2}) time but with O*(2^{n/2}) space; Schroeppel–Shamir improves the space to O*(2^{n/4}) while maintaining the same time bound.

Garey & Johnson classification: The issue correctly identifies Partition as A3 SP12 (though the standard numbering is SP2 for the basic Partition problem; SP12 is a related variant). The definition matches the standard formulation.

NP-completeness: Confirmed — Partition is one of Karp's original 21 NP-complete problems (1972), reduced from 3-Dimensional Matching via Exact Cover → Knapsack → Partition in Karp's tree.

Well-written

Strengths:

• Definition section is clear and mathematically precise
• Variables section correctly describes the binary encoding
• Example is non-trivial (n=6 elements), hand-verifiable, and fully worked
• Schema is clean and simple
• How-to-solve section has both brute-force and ILP checked, plus the pseudo-polynomial DP noted

Minor issues (warnings, not failures):

1. Trait choice unclear: The issue defines Partition as a satisfaction (decision) problem (QUESTION: "Is there a subset...?"), which means it should implement SatisfactionProblem with Metric = bool. This is consistent with the definition but is not explicitly stated in the issue. The implementer should use SatisfactionProblem, not OptimizationProblem.

2. Size field naming: The schema lists a sizes field. For the declare_variants! complexity string, the getter would be num_elements (matching sizes.len()). The issue should clarify this getter name since the overhead system validates variable names at compile time. The complexity string would be "2^(num_elements / 2)" (matching Knapsack's pattern of "2^(num_items / 2)").

3. Minor bibliographic error: The Schroeppel–Shamir citation says "10(4)" but the correct issue number is 3, not 4 (SIAM J. Comput. Vol. 10, No. 3).

4. AI-generated warnings: Multiple sections are marked with "Unverified: AI-generated" warnings. This is honest but the content should be verified before implementation.

Recommendations

• Explicitly state that Partition implements SatisfactionProblem (Metric = bool), not OptimizationProblem.
• Define the getter method name num_elements() in the schema section for clarity.
• Fix the Schroeppel–Shamir issue number: 10(3):456–464, not 10(4).
• Consider planned reduction rules: Knapsack → Partition and Partition → BinPacking would be natural additions to connect this problem in the reduction graph.