Source: SUBSET SUM (SubsetSum)
Target: INTEGER KNAPSACK (IntegerKnapsack)
Motivation: Establishes NP-completeness of INTEGER KNAPSACK by direct embedding of SUBSET SUM. Each element maps to a knapsack item with equal size and value (s(u) = v(u) = a_i), capacity equals the target sum, and the value target equals B. The exact-sum constraint forces 0-1 multiplicities in the forward direction. This is one of the simplest NP-completeness reductions, connecting the fundamental exact-sum problem to the richer integer knapsack framework.
Reference: Garey & Johnson, Computers and Intractability, A6, MP10; Lueker (1975).
GJ Source Entry
[MP10] INTEGER KNAPSACK
INSTANCE: Finite set U, for each u ∈ U a size s(u) ∈ Z^+ and a value v(u) ∈ Z^+, and positive integers B and K.
QUESTION: Is there an assignment of a non-negative integer c(u) to each u ∈ U such that Σ_{u ∈ U} c(u)·s(u) ≤ B and Σ_{u ∈ U} c(u)·v(u) ≥ K?
Reference: [Lueker, 1975]. Transformation from SUBSET SUM.
Comment: Remains NP-complete if s(u) = v(u) for all u ∈ U. Solvable in pseudo-polynomial time by dynamic programming.
Reduction Algorithm
Given a SubsetSum instance with elements A = {a_1, ..., a_n} with sizes s(a_i) and target B, construct an IntegerKnapsack instance as follows:
-
Item set: Create n items. Item u_i has size s(u_i) = s(a_i) and value v(u_i) = s(a_i). That is, size equals value for every item.
-
Capacity: Set knapsack capacity to B (the SubsetSum target).
-
Value target: The IntegerKnapsack objective is to maximize total value. Since s = v for all items, the capacity constraint Σ c(u_i)·s(u_i) ≤ B and value maximization Σ c(u_i)·v(u_i) together aim to pack as close to B as possible.
-
Forward direction (SubsetSum YES → IntegerKnapsack achieves B): If A' ⊆ A sums to exactly B, set c(u_i) = 1 for a_i ∈ A' and c(u_i) = 0 otherwise. Total size = B ≤ B, total value = B.
-
Backward direction concern: The IntegerKnapsack allows integer multiplicities c(u_i) ≥ 0, not just 0-1. A knapsack solution achieving value ≥ B with total size ≤ B might use c(u_i) > 1. Since s = v, this means total size = total value, so the solution achieves exactly B. But the multiplicities may not correspond to a 0-1 subset.
-
Solution extraction: From a knapsack solution with multiplicities c(u_i), define A' = {a_i : c(u_i) ≥ 1}. If Σ_{a ∈ A'} s(a) = B, this is a valid SubsetSum solution. If Σ_{a ∈ A'} s(a) > B (because some c(u_i) > 1), greedily reduce multiplicities to 1; if the resulting sum drops below B, the original SubsetSum may have no solution despite the knapsack achieving B.
Correctness
The forward direction is clean: SubsetSum YES implies IntegerKnapsack achieves value B. The backward direction has a gap when multiplicities exceed 1. The reduction proves NP-hardness (one direction): SubsetSum ≤_p IntegerKnapsack.
Counterexample for backward direction: A = {3}, B = 6. SubsetSum answer is NO (only element has size 3 ≠ 6). But IntegerKnapsack allows c(u_1) = 2, giving total size = 6 = B and total value = 6 ≥ B. The knapsack says "achievable" but the SubsetSum says NO.
Codex verification needed: Need to check if the codebase's IntegerKnapsack model restricts multiplicities (0-1 knapsack vs unbounded). If multiplicities are unrestricted, the backward direction fails for witness extraction. The forward direction (NP-hardness proof) is still valid.
Size Overhead
| Target metric (code name) |
Expression |
num_items |
num_elements |
capacity |
target_sum |
Derivation: One knapsack item per SubsetSum element. Capacity equals the target sum. No blowup in any dimension.
Implementation Note
IntegerKnapsack currently has 0 outgoing reductions (no ILP solver). An IntegerKnapsack → ILP rule should be implemented alongside this rule:
- Integer variable c_i ≥ 0 per item (multiplicity)
- Capacity constraint: Σ c_i · s(u_i) ≤ B
- Objective: maximize Σ c_i · v(u_i) (Value = Max)
- Upper bound on each c_i: c_i ≤ floor(B / s(u_i)) (tighten the LP relaxation)
- Overhead:
num_vars = "num_items", constraints = O(num_items)
Example
Source (SubsetSum):
A = {a_1, a_2, a_3, a_4, a_5} with sizes s = [3, 7, 1, 8, 5], target B = 16.
- Valid subset: A' = {a_1, a_4, a_5} → 3 + 8 + 5 = 16 ✓
- Another solution: A' = {a_2, a_4, a_5}? → 7 + 8 + 5 = 20 ≠ 16 ✗
- Another solution: A' = {a_2, a_3, a_4}? → 7 + 1 + 8 = 16 ✓
Target (IntegerKnapsack):
- 5 items: sizes = [3, 7, 1, 8, 5], values = [3, 7, 1, 8, 5]
- Capacity B = 16
Solution mapping (forward):
- SubsetSum A' = {a_1, a_4, a_5}: c = [1, 0, 0, 1, 1]
- Total size: 3 + 8 + 5 = 16 ≤ 16 ✓
- Total value: 3 + 8 + 5 = 16 (maximum achievable = B)
Counterexample demonstrating backward gap:
- Source: A = {3}, B = 6
- Target: 1 item, size = value = 3, capacity = 6
- Knapsack optimal: c = [2], total size = 6 ≤ 6, total value = 6 ≥ 6 ✓
- But SubsetSum has no solution: {3} cannot sum to 6 with 0-1 multiplicities ✗
- This demonstrates that the backward witness extraction fails when multiplicities > 1
No-instance:
- Source: A = {3, 7, 1, 8, 5}, B = 2
- No subset sums to exactly 2 (smallest element is 1, next is 3, and 1 ≠ 2)
- Actually {1} doesn't sum to 2. No valid subset ✗
- Target: knapsack with capacity 2, best is c = [0, 0, 1, 0, 0], value = 1 < 2
- Knapsack confirms NO ✓ (when restricted to 0-1 multiplicities; with unbounded multiplicities, still max value = 1 since only item 3 fits)
Wait — item 3 has size 1, so c(u_3) = 2 gives size = 2 ≤ 2 and value = 2 ≥ 2. The unbounded knapsack says YES but SubsetSum says NO. This is another instance of the backward gap.
Validation Method
- Closed-loop test: reduce SubsetSum to IntegerKnapsack, solve target via ILP (IntegerKnapsack → ILP), extract subset from items with c(u_i) ≥ 1, verify sizes sum to B
- Test both YES and NO instances
- Explicitly test the counterexample {3}, B=6 to verify behavior with unrestricted multiplicities
- Verify item counts and capacity match overhead formulas
References
- Lueker, G. S. (1975). "Two NP-complete problems in nonnegative integer programming." Computer Science Laboratory, Princeton University.
- Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability, A6, MP10, p.247.
Source: SUBSET SUM (SubsetSum)
Target: INTEGER KNAPSACK (IntegerKnapsack)
Motivation: Establishes NP-completeness of INTEGER KNAPSACK by direct embedding of SUBSET SUM. Each element maps to a knapsack item with equal size and value (s(u) = v(u) = a_i), capacity equals the target sum, and the value target equals B. The exact-sum constraint forces 0-1 multiplicities in the forward direction. This is one of the simplest NP-completeness reductions, connecting the fundamental exact-sum problem to the richer integer knapsack framework.
Reference: Garey & Johnson, Computers and Intractability, A6, MP10; Lueker (1975).
GJ Source Entry
Reduction Algorithm
Given a
SubsetSuminstance with elements A = {a_1, ..., a_n} with sizes s(a_i) and target B, construct anIntegerKnapsackinstance as follows:Item set: Create n items. Item u_i has size s(u_i) = s(a_i) and value v(u_i) = s(a_i). That is, size equals value for every item.
Capacity: Set knapsack capacity to B (the SubsetSum target).
Value target: The IntegerKnapsack objective is to maximize total value. Since s = v for all items, the capacity constraint Σ c(u_i)·s(u_i) ≤ B and value maximization Σ c(u_i)·v(u_i) together aim to pack as close to B as possible.
Forward direction (SubsetSum YES → IntegerKnapsack achieves B): If A' ⊆ A sums to exactly B, set c(u_i) = 1 for a_i ∈ A' and c(u_i) = 0 otherwise. Total size = B ≤ B, total value = B.
Backward direction concern: The IntegerKnapsack allows integer multiplicities c(u_i) ≥ 0, not just 0-1. A knapsack solution achieving value ≥ B with total size ≤ B might use c(u_i) > 1. Since s = v, this means total size = total value, so the solution achieves exactly B. But the multiplicities may not correspond to a 0-1 subset.
Solution extraction: From a knapsack solution with multiplicities c(u_i), define A' = {a_i : c(u_i) ≥ 1}. If Σ_{a ∈ A'} s(a) = B, this is a valid SubsetSum solution. If Σ_{a ∈ A'} s(a) > B (because some c(u_i) > 1), greedily reduce multiplicities to 1; if the resulting sum drops below B, the original SubsetSum may have no solution despite the knapsack achieving B.
Correctness
The forward direction is clean: SubsetSum YES implies IntegerKnapsack achieves value B. The backward direction has a gap when multiplicities exceed 1. The reduction proves NP-hardness (one direction): SubsetSum ≤_p IntegerKnapsack.
Counterexample for backward direction: A = {3}, B = 6. SubsetSum answer is NO (only element has size 3 ≠ 6). But IntegerKnapsack allows c(u_1) = 2, giving total size = 6 = B and total value = 6 ≥ B. The knapsack says "achievable" but the SubsetSum says NO.
Codex verification needed: Need to check if the codebase's
IntegerKnapsackmodel restricts multiplicities (0-1 knapsack vs unbounded). If multiplicities are unrestricted, the backward direction fails for witness extraction. The forward direction (NP-hardness proof) is still valid.Size Overhead
num_itemsnum_elementscapacitytarget_sumDerivation: One knapsack item per SubsetSum element. Capacity equals the target sum. No blowup in any dimension.
Implementation Note
IntegerKnapsack currently has 0 outgoing reductions (no ILP solver). An IntegerKnapsack → ILP rule should be implemented alongside this rule:
num_vars = "num_items", constraints = O(num_items)Example
Source (SubsetSum):
A = {a_1, a_2, a_3, a_4, a_5} with sizes s = [3, 7, 1, 8, 5], target B = 16.
Target (IntegerKnapsack):
Solution mapping (forward):
Counterexample demonstrating backward gap:
No-instance:
Wait — item 3 has size 1, so c(u_3) = 2 gives size = 2 ≤ 2 and value = 2 ≥ 2. The unbounded knapsack says YES but SubsetSum says NO. This is another instance of the backward gap.
Validation Method
References