Motivation
Classic NP-hard problem from number theory; foundational in cryptography and has direct reductions to ILP and QUBO. Opens the number-theoretic domain for the reduction graph.
Definition
Name: SubsetSum
Reference: Garey & Johnson (1979), SP13; https://en.wikipedia.org/wiki/Subset_sum_problem
Given a set of integers $S = {s_1, s_2, \ldots, s_n}$ and a target value $T$, determine if there exists a subset $S' \subseteq S$ such that $\sum_{s \in S'} s = T$.
Variables
-
Count: $n = |S|$ (one variable per element)
-
Per-variable domain: binary ${0, 1}$
-
Meaning: $x_i = 1$ if element $s_i$ is selected in the subset
Schema (data type)
Type name: SubsetSum
Variants: weight type (i32)
| Field |
Type |
Description |
| elements |
Vec<i32> |
the set $S$ of integers |
| target |
i32 |
the target sum $T$
|
Problem Size
| Metric |
Expression |
Description |
| num_elements |
$ |
S |
Complexity
-
Decision complexity: NP-complete (weakly NP-hard)
-
Best known exact algorithm: $O(2^{n/2})$ via meet-in-the-middle (Horowitz & Sahni, 1974)
-
Best known approximation: FPTAS exists since SubsetSum is weakly NP-hard
How to solve
Example Instance
$S = {3, 7, 1, 8, 4}$, $T = 12$.
Solutions: ${1, 3, 8}$ ($x = [1,0,1,1,0]$) and ${8, 4}$ ($x = [0,0,0,1,1]$) and ${1, 7, 4}$ ($x = [0,1,1,0,1]$).
Motivation
Classic NP-hard problem from number theory; foundational in cryptography and has direct reductions to ILP and QUBO. Opens the number-theoretic domain for the reduction graph.
Definition
Name: SubsetSum
Reference: Garey & Johnson (1979), SP13; https://en.wikipedia.org/wiki/Subset_sum_problem
Given a set of integers$S = {s_1, s_2, \ldots, s_n}$ and a target value $T$ , determine if there exists a subset $S' \subseteq S$ such that $\sum_{s \in S'} s = T$ .
Variables
Schema (data type)
Type name: SubsetSum
Variants: weight type (i32)
Vec<i32>i32Problem Size
Complexity
How to solve
Example Instance
Solutions:${1, 3, 8}$ ($x = [1,0,1,1,0]$ ) and ${8, 4}$ ($x = [0,0,0,1,1]$ ) and ${1, 7, 4}$ ($x = [0,1,1,0,1]$ ).