[Model] 3Partition

[isPANN]

Motivation

3-PARTITION (P142) from Garey & Johnson, A3 SP15. A classical strongly NP-complete problem: given 3m positive integers with each between B/4 and B/2 and total sum mB, can they be partitioned into m triples each summing to B? Unlike the standard PARTITION problem (which is only weakly NP-hard), 3-PARTITION has no pseudo-polynomial-time algorithm unless P = NP. This makes it the canonical source for strong NP-completeness reductions, especially to scheduling and packing problems.

Associated rules (as source):

• R66: 3-Partition -> Intersection Graph for Segments on a Grid
• R67: 3-Partition -> Edge Embedding on a Grid
• R80: 3DM -> 3-Partition (3-Partition as target)
• R88: 3-Partition -> Dynamic Storage Allocation
• R98: Partition / 3-Partition -> Expected Retrieval Cost
• R131: 3-Partition -> Sequencing with Release Times and Deadlines
• R135: 3-Partition -> Sequencing to Minimize Weighted Tardiness
• R139: 3-Partition -> Resource Constrained Scheduling
• R144: 3-Partition -> Flow-Shop Scheduling
• R147: 3-Partition -> Job-Shop Scheduling
• R232: 3-Partition -> Bandwidth
• R233: 3-Partition -> Directed Bandwidth
• R234: 3-Partition -> Weighted Diameter

Definition

Name: ThreePartition

Reference: Garey & Johnson, Computers and Intractability, A3 SP15

Mathematical definition:

INSTANCE: Set A of 3m elements, a bound B in Z^+, and a size s(a) in Z^+ for each a in A such that B/4 < s(a) < B/2 and such that sum_{a in A} s(a) = mB.
QUESTION: Can A be partitioned into m disjoint sets A_1,A_2,...,A_m such that, for 1 <= i <= m, sum_{a in A_i} s(a) = B (note that each A_i must therefore contain exactly three elements from A)?

Variables

• Count: 3m (one variable per element, assigning it to a group)
• Per-variable domain: {1, 2, ..., m} -- the group index to which the element is assigned
• Meaning: g_i in {1,...,m} is the group for element a_i. The assignment is feasible iff each group contains exactly 3 elements and sum_{j: g_j = k} s(a_j) = B for all k in {1,...,m}.

Schema (data type)

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

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

Note: The constraint B/4 < s(a) < B/2 and sum = mB are invariants that should be validated on construction. The number of groups m = sizes.len() / 3.

Complexity

• Best known exact algorithm: 3-PARTITION is strongly NP-complete, meaning no pseudo-polynomial-time algorithm exists unless P = NP. The subset dynamic programming approach assigns each element to one of approximately 3 states, yielding a worst-case time complexity of O(3^n) where n = 3m is the number of elements. The brute-force approach enumerates all ways to partition 3m elements into m triples, which is O((3m)! / (3!)^m / m!) -- exponential. Because the problem is strongly NP-complete, no algorithm with running time polynomial in the input size (even when numbers are encoded in unary) is known. [Garey & Johnson, 1975; Garey & Johnson, Computers and Intractability, 1979.]
• Concrete complexity expression: 3^num_elements

Extra Remark

Full book text:

INSTANCE: Set A of 3m elements, a bound B in Z^+, and a size s(a) in Z^+ for each a in A such that B/4 < s(a) < B/2 and such that sum_{a in A} s(a) = mB.
QUESTION: Can A be partitioned into m disjoint sets A_1,A_2,...,A_m such that, for 1 <= i <= m, sum_{a in A_i} s(a) = B (note that each A_i must therefore contain exactly three elements from A)?
Reference: [Garey and Johnson, 1975]. Transformation from 3DM (see Section 4.2).
Comment: NP-complete in the strong sense.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all partitions of 3m elements into m triples; check if each triple sums to B.)
• It can be solved by reducing to integer programming. (Binary ILP: x_{i,k} in {0,1}, sum_k x_{i,k} = 1 for each i, sum_i x_{i,k} = 3 for each k, sum_i x_{i,k} * s(a_i) = B for each k.)
• Other: Dynamic programming over subset sums (pseudo-polynomial, O(n * B^(m-1))).

Example Instance

Input:
A = {a_1, ..., a_6} (3m = 6 elements, so m = 2)
B = 15
Sizes: s(a_1) = 4, s(a_2) = 5, s(a_3) = 6, s(a_4) = 4, s(a_5) = 6, s(a_6) = 5

• All sizes satisfy B/4 = 3.75 < s(a_i) < B/2 = 7.5 (strict inequalities hold for all elements)
• Total sum = 4 + 5 + 6 + 4 + 6 + 5 = 30 = 2 * 15 = mB

Feasible assignment:
A_1 = {a_1, a_2, a_3} = {4, 5, 6} (sum = 15 = B)
A_2 = {a_4, a_5, a_6} = {4, 6, 5} (sum = 15 = B)

Answer: YES -- a valid 3-partition exists.

Non-triviality: Of the 10 possible ways to partition 6 elements into 2 groups of 3, exactly 4 are valid 3-partitions (40%), while the remaining 6 are not -- providing a good mix for round-trip testing.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; classic strongly NP-complete problem with many planned reductions
Non-trivial	✅ Pass	Distinct from existing BinPacking and Knapsack — unique 3-element-per-group constraint with size bounds
Correctness	❌ Fail	Example instance violates the strict inequality constraint B/4 < s(a)
Well-written	⚠️ Warn	Complexity section lacks a concrete time bound for declare_variants!

Overall: 2 passed, 1 failed, 1 warning

---

Usefulness

ThreePartition does not exist in the codebase. It is a classical strongly NP-complete problem (Garey & Johnson A3 SP15) that serves as the canonical source for strong NP-completeness reductions to scheduling and packing problems. The issue lists 13+ associated reduction rules, making it a high-value addition to the reduction graph.

Non-trivial

ThreePartition is genuinely distinct from all existing problems:

• Not BinPacking: BinPacking minimizes the number of bins; ThreePartition requires exactly m groups of exactly 3 elements each summing to B, with strict size bounds B/4 < s(a) < B/2.
• Not Knapsack: Knapsack is a single-container optimization; ThreePartition is a multi-group satisfaction problem.
• The feasibility constraints (exactly 3 elements per group, strict size bounds, exact sum) are unique.

Correctness

Reference verification:

• Garey & Johnson 1979 textbook: Confirmed, already in project bibliography as garey1979.
• Garey & Johnson 1975 paper: Real — "Complexity results for multiprocessor scheduling under resource constraints," SIAM J. Computing, vol. 4, pp. 397-411, 1975. Proves 3-Partition NP-complete via reduction from 3-Dimensional Matching.
• Strong NP-completeness claim: Correct and well-established.

Example instance error:
The example sets s(a_3) = 3, but the constraint requires B/4 < s(a) (strict inequality). With B = 12, B/4 = 3, so s(a_3) = 3 does NOT satisfy B/4 < s(a_3). The value must be strictly greater than 3 (e.g., s(a_3) = 4). This invalidates the example.

A corrected example could use: sizes = [4, 5, 3, 4, 4, 4] replaced with e.g. sizes = [4, 4, 4, 4, 5, 3] where all satisfy the strict bounds — but actually 3 still fails. A valid example with B = 12 needs all sizes in {4, 5} (integers strictly between 3 and 6). For instance: sizes = [4, 4, 4, 4, 4, 4] with A_1 = A_2 = {4, 4, 4}, sum = 12 each.

Well-written

Sections present: All required template sections are filled in. The ⚠️ Unverified markers are appreciated for transparency.

Complexity section weakness: The section discusses strong NP-completeness and mentions brute-force enumeration and DP approaches, but does not provide a specific best-known exact algorithm time bound suitable for declare_variants!. For implementation, a concrete expression like "2^num_elements" or similar is needed. The DP bound O(n * B^(m-1)) is pseudo-polynomial, which is not appropriate for a strongly NP-hard problem's worst-case complexity.

Other minor items:

• Schema looks reasonable; Vec<u64> for sizes and u64 for bound are appropriate types.
• Variable encoding as group assignment {1,...,m} is clear and implementable.
• ILP formulation in "How to solve" is correct.

Recommendations

• Fix the example to use sizes that all strictly satisfy B/4 < s(a) < B/2.
• Add a concrete worst-case complexity bound for the best known exact algorithm (e.g., based on subset enumeration approaches).

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; 13+ planned reductions
Non-trivial	✅ Pass	Distinct from Partition, BinPacking, Knapsack — unique 3-per-group + size bounds
Correctness	✅ Pass	All references verified (Garey & Johnson 1975, 1979); strong NP-completeness confirmed
Well-written	❌ Fail	Example violates strict inequality constraint; complexity lacks concrete bound

Overall: 3 passed, 1 failed

Re-check requested with --force. Previous check (2026-03-12): 2 passed, 1 failed, 1 warning. Change: Correctness reclassified from Fail → Pass (references are correct; the example constraint violation properly belongs under Well-written/Example Quality).

---

Usefulness

ThreePartition does not exist in the codebase (pred show ThreePartition fails). It is a classical strongly NP-complete problem (Garey & Johnson A3 [SP15]) that is the canonical source for strong NP-completeness reductions to scheduling and packing problems. The issue lists 13+ associated reduction rules (R66, R67, R80, R88, R98, R131, R135, R139, R144, R147, R232, R233, R234), making it a high-value hub in the reduction graph.

Non-trivial

ThreePartition is genuinely distinct from all existing problems:

• Not Partition: Partition splits into 2 equal-sum subsets with no group-size constraint and no per-element size bounds. Partition is only weakly NP-hard (admits pseudo-polynomial DP); ThreePartition is strongly NP-complete.
• Not BinPacking: BinPacking minimizes the number of bins (optimization); ThreePartition requires exactly m groups of exactly 3 elements (satisfaction), with strict size bounds B/4 < s(a) < B/2.
• Not Knapsack: Single-container optimization problem.
• Not SumOfSquaresPartition / GraphPartitioning: Different objectives and input structures entirely.

The unique combination of exactly-3-per-group, strict size bounds, and exact target sum makes this a distinct problem.

Correctness

Reference verification:

• Garey & Johnson 1979 textbook: Confirmed. Already in project bibliography as garey1979. 3-Partition is cataloged as [SP15] under section A3.2 (Number Problems / Weighted Set Problems).
• Garey & Johnson 1975 paper: Confirmed. "Complexity Results for Multiprocessor Scheduling under Resource Constraints," SIAM J. Computing, vol. 4, no. 4, pp. 397-411. Verified via DBLP and SIAM. Proves 3-Partition NP-complete.
• Strong NP-completeness: Confirmed. Well-established result — no pseudo-polynomial-time algorithm unless P = NP.
• 3DM reduction: Confirmed with nuance. The 1975 paper reduces from 3DM directly. The 1979 book refines this as 3DM → 4-Partition → 3-Partition (two-step chain). Both are valid.

Representation feasibility: Vec<u64> for sizes and u64 for bound are appropriate for positive integers.

Well-written

4a — Information Completeness: All required sections are present and substantive. The ⚠️ Unverified markers show good transparency. ✅

4b — Definition Completeness: The formal definition is precise, directly from G&J, with clear feasibility constraints. ✅

4c — Symbol and Notation Consistency: Symbols (A, B, m, s(a), A_i) are used consistently across sections. ✅

4d — Example Quality: ❌ Fail

Python validation (brute-force enumeration of all 10 possible partitions of 6 elements into 2 groups of 3):

• Constraint violation: s(a_3) = 3 violates the strict inequality B/4 < s(a). With B = 12, B/4 = 3.0, so the constraint requires s(a) > 3 (strictly greater). The value 3 is exactly equal to the lower bound, not strictly greater. The issue itself states "B/4 = 3 < s(a_i)" which is incorrect for a_3.
• Otherwise valid: The claimed partition {4,5,3} + {4,4,4} does sum to 12 each. The total sum 24 = 2×12 = mB is correct. Non-triviality is good: 4/10 partitions satisfy the sum constraint (good mix of satisfying/non-satisfying).
• Fix needed: All sizes must be integers in the open interval (3, 6) for B = 12, i.e., {4, 5}. A valid corrected example: sizes = [4, 4, 4, 4, 4, 4] with trivial partition, or increase B to allow more variety (e.g., B = 20 with sizes from {6,7,8,9}).

Complexity section: ⚠️ Warn

The section discusses strong NP-completeness and mentions brute-force and DP approaches, but does not provide a concrete worst-case time bound for declare_variants!. Research suggests 3^num_elements (subset DP over triple assignments) is the tightest clean bound. The DP bound O(n × B^(m-1)) is pseudo-polynomial and inappropriate for a strongly NP-hard problem's worst-case characterization.

Recommendations

• Fix the example: Replace sizes so all strictly satisfy B/4 < s(a) < B/2. Consider using B = 20 (sizes must be in {6,7,8,9}) for a more interesting example with diverse values.
• Add a concrete complexity expression: e.g., "3^num_elements" (subset DP) or "(num_elements / 3)^num_elements" (brute-force group assignment), with a brief citation.

[isPANN]

Fix-issue changelog

• Example fixed: Changed B from 12 to 15, sizes from [4,5,3,4,4,4] to [4,5,6,4,6,5]. All sizes now strictly satisfy B/4 = 3.75 < s(a) < B/2 = 7.5. Added non-triviality stats (4/10 valid partitions, 40%).
• Complexity bound added: Added concrete expression 3^num_elements (subset DP approach, O(3^n) where n = 3m) for declare_variants!.

Applied by /fix-issue.