[Model] SubsetSum

[GiggleLiu]

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

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming, through a new SubsetSum → ILP rule issue (to be filed).

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]$).