[Model] SubsetProduct

[isPANN]

Motivation

SUBSET PRODUCT (P141) from Garey & Johnson, A3 SP14. Given a finite set A of positive integers and a target product B, determine whether there exists a subset whose product equals B. NP-complete in the strong sense (unlike Subset Sum, which is only weakly NP-complete), because the multiplicative structure prevents pseudo-polynomial dynamic programming. NP-completeness is established by transformation from Exact Cover by 3-Sets (Yao, 1978).

Associated rules:

• [Rule] EXACT COVER BY 3-SETS to SUBSET PRODUCT #858 / [Rule] EXACT COVER BY 3-SETS to SUBSET PRODUCT #388: ExactCoverBy3Sets → SubsetProduct (classical NP-completeness proof from G&J)

Definition

Name: SubsetProduct
Reference: Garey & Johnson, Computers and Intractability, A3 SP14

Mathematical definition:

INSTANCE: Finite set A, a size s(a) ∈ Z^+ for each a ∈ A, and a positive integer B.
QUESTION: Is there a subset A' ⊆ A such that the product of the sizes of the elements in A' is exactly B?

Variables

• Count: |A| (number of elements in the set)
• Per-variable domain: {0, 1}
• Meaning: Whether each element a ∈ A is included in the subset A'.

Schema (data type)

Type name: SubsetProduct
Variants: None (single variant).

Field	Type	Description
sizes	Vec<BigUint>	The sizes s(a) for each element a ∈ A
target	BigUint	The target product B

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_elements() (= |A|).
• Uses BigUint because products grow exponentially fast — even modest-sized instances can exceed u64::MAX. Consistent with the existing SubsetSum implementation.

Complexity

• Decision complexity: NP-complete in the strong sense (Yao, 1978; transformation from Exact Cover by 3-Sets). Unlike Subset Sum, no pseudo-polynomial dynamic programming algorithm exists unless P = NP.
• Best known exact algorithm: O*(2^(n/2)) via meet-in-the-middle — enumerate all subset products of each half, then search for complementary pairs where p1 * p2 = B. This generalizes the Horowitz-Sahni (1974) approach for Subset Sum to the multiplicative case.
• Concrete complexity expression: "2^(0.5 * num_elements)" (for declare_variants!)
• References:
  • A.C. Yao (1978). "On the complexity of comparison problems using linear functions." In Proc. 10th Annual ACM Symposium on Theory of Computing (STOC), pp. 85-89.
  • E. Horowitz, S. Sahni (1974). "Computing partitions with applications to the knapsack problem." J. ACM 21(2), pp. 277-292.
  • M.R. Garey and D.S. Johnson (1979). Computers and Intractability. W.H. Freeman.

Extra Remark

Full book text:

INSTANCE: Finite set A, a size s(a) ∈ Z^+ for each a ∈ A, and a positive integer B.
QUESTION: Is there a subset A' ⊆ A such that the product of the sizes of the elements in A' is exactly B?
Reference: [Yao, 1978b]. Transformation from X3C.
Comment: NP-complete in the strong sense.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^|A| subsets; compute the product of each and check against B.)
• It can be solved by reducing to integer programming.
• Other: Meet-in-the-middle in O*(2^(n/2)).

Example Instance

Input:
A = {a_1, ..., a_6} with sizes s = [2, 3, 5, 7, 6, 10], target product B = 210.

Valid subset: A' = {a_1, a_2, a_3, a_4} with sizes {2, 3, 5, 7}.
Product: 2 × 3 × 5 × 7 = 210 = B. ✓
Answer: YES.

Note: The solution is not unique — {3, 10, 7} gives 3 × 10 × 7 = 210, and {5, 6, 7} gives 5 × 6 × 7 = 210. There are 3 valid subsets out of 64 total.

Negative example:
Same elements s = [2, 3, 5, 7, 6, 10], target product B = 211.
Since 211 is prime and does not appear in the element set, no subset product can equal 211. (Any subset product is a product of elements from {2,3,5,6,7,10}, which factors only over primes {2,3,5,7}. Since 211 is prime and not in {2,3,5,7}, it cannot be achieved.)
Answer: NO.

Python validation script

from itertools import combinations
from math import prod

sizes = [2, 3, 5, 7, 6, 10]

# Positive: B = 210
valid_210 = []
for r in range(len(sizes)+1):
    for combo in combinations(range(len(sizes)), r):
        if prod(sizes[i] for i in combo) == 210:
            valid_210.append([sizes[i] for i in combo])
assert len(valid_210) == 3
print(f"B=210: {len(valid_210)} valid subsets: {valid_210}")

# Negative: B = 211
valid_211 = []
for r in range(len(sizes)+1):
    for combo in combinations(range(len(sizes)), r):
        if prod(sizes[i] for i in combo) == 211:
            valid_211.append([sizes[i] for i in combo])
assert len(valid_211) == 0
print(f"B=211: {len(valid_211)} valid subsets (correct: NO)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting SubsetProduct to existing graph
Non-trivial	✅ Pass	Distinct from all existing problems (multiplicative vs additive)
Correctness	⚠️ Warn	Yao 1978 reference not independently verified; complexity bound plausible but not confirmed in literature; u64 may overflow
Well-written	❌ Fail	Missing Expected Outcome section; no concrete complexity expression for declare_variants!; u64 should be BigUint

Overall: 1 passed, 2 failed, 1 warning

---

Usefulness

Fail. The Motivation section says SubsetProduct is "useful for reductions" but does not name any concrete reduction rule connecting this problem to an existing problem in the reduction graph. A problem without at least one planned reduction to/from an existing node is an orphan and has no value in the graph.

To fix: add at least one specific planned reduction. Natural candidates include:

• SubsetProduct can be reduced from ExactCoverBy3Sets (X3C) — this is the original NP-completeness proof by Yao (1978)
• SubsetProduct can be reduced to ILP (by taking logarithms and using integer constraints, though care is needed for exactness)
• SubsetProduct could potentially connect to SubsetSum via logarithmic transformation (though rounding issues make this non-trivial)

Non-trivial

Pass. SubsetProduct has a genuinely different feasibility constraint from all existing problems. The closest existing problem is SubsetSum, which uses additive combination (sum), whereas SubsetProduct uses multiplicative combination (product). These are structurally different — the multiplicative structure makes SubsetProduct strongly NP-complete while SubsetSum is only weakly NP-complete, and different algorithmic techniques apply.

Correctness

Warn. Several items could not be fully verified:

1. Yao 1978 reference: The issue cites "Yao, 1978b" as the source of the NP-completeness proof via transformation from X3C. This matches what Garey & Johnson list for SP14, but the specific paper could not be independently located online to verify the exact claim. The reference is likely Andrew Yao, but the specific paper title and venue are not provided in the issue.

2. Strong NP-completeness: The claim that SubsetProduct is NP-complete in the strong sense is consistent with Garey & Johnson's classification and is supported by the literature — the multiplicative structure prevents the standard DP table approach used for additive problems like Subset Sum.

3. Complexity bound O*(2^(n/2)): The meet-in-the-middle approach is plausible for SubsetProduct (enumerate subset products of each half, then search for complementary pairs where p1 * p2 = B). However, no specific citation is provided for this algorithm applied to the multiplicative case. For Subset Sum, the 2^(n/2) bound is due to Horowitz-Sahni (1974), and the approach generalizes naturally to products.

4. Data type u64: Products grow exponentially fast. Even with modest element sizes, a subset of ~20 elements with values around 10 can produce products exceeding u64::MAX (≈1.8 * 10^19). The existing SubsetSum implementation uses BigUint for exactly this reason. Using u64 limits the practical domain and risks silent overflow. Recommendation: Use BigUint instead of u64, consistent with SubsetSum.

Well-written

Fail. Several template sections are missing or incomplete:

1. Missing Expected Outcome section: The Example Instance section says "Answer: YES" inline, but there is no dedicated Expected Outcome section. For a satisfaction problem, this should explicitly state one valid/satisfying solution with justification for why it satisfies the constraints.

2. No concrete complexity expression: The Complexity section describes the bound in prose ("O*(2^(n/2)) via meet-in-the-middle") but does not provide a concrete expression in terms of problem-parameter getter names suitable for declare_variants!. It should be something like 2^(0.5 * num_elements).

3. Data type mismatch: The Schema proposes Vec<u64> and u64, but as noted in Correctness, BigUint would be more appropriate and consistent with the existing SubsetSum implementation. The Schema should match the actual implementation type.

4. Example quality: The example is adequate — 6 elements, 3 satisfying solutions out of 64 total configurations, which provides meaningful testing coverage. However, the issue could benefit from showing one non-satisfying subset to illustrate the constraint more clearly.

5. Symbol consistency: The mathematical definition uses s(a) for element sizes, but the Schema uses elements as the field name. While not a strict inconsistency, using sizes (as the definition calls them) would be more consistent — matching the SubsetSum convention of sizes field name.

Recommendations

• Provide the full citation for Yao 1978 (title, venue, pages) rather than just "Yao, 1978b"
• Consider adding the Horowitz-Sahni (1974) reference for the meet-in-the-middle algorithm
• Rename the elements field to sizes for consistency with SubsetSum and the mathematical definition
• Use BigUint instead of u64 for both sizes and target fields

[isPANN]

Fix-issue changelog

• Motivation: Rewrote vague text with concrete context: strong NP-completeness contrast with SubsetSum, X3C transformation.
• Associated rules: Linked existing rule issues [Rule] EXACT COVER BY 3-SETS to SUBSET PRODUCT #858 and [Rule] EXACT COVER BY 3-SETS to SUBSET PRODUCT #388 (ExactCoverBy3Sets → SubsetProduct).
• Schema: Renamed elements → sizes (matches mathematical definition and SubsetSum convention); changed u64 → BigUint (products grow exponentially, consistent with SubsetSum).
• Complexity: Added concrete expression "2^(0.5 * num_elements)" for declare_variants!; added Horowitz-Sahni and Yao references.
• Example: Added negative example (B=211 is prime, not achievable from {2,3,5,7} prime factors); added non-trivial analysis (3/64 valid subsets).
• Added Python validation script verifying both positive (3 valid) and negative (0 valid) cases.

Applied by /fix-issue.