Subset Sum Problem

Definition

Subset Sum Problem

Let $S=\{w_1,\dots ,w_n\}$ be a multiset of positive integers and $W\in {\mathbb{Z}}^{+}$ be a target sum. The subset sum problem is a decision problem asking whether there exists a subset $S^{\prime }\subseteq S$ such that the sum of the elements in $S^{\prime }$ is exactly $W$:
${\sum }_{w\in S^{\prime }}w=W$

NP-completeness

Subset Sum belongs to NP because a selected submultiset is a polynomial-size certificate whose sum can be checked in polynomial time. Its NP-hardness follows from the reduction from 3-SAT.

Definition

3-SAT to Subset Sum

There is a polynomial-time many-one reduction from the 3-SAT problem to the Subset Sum problem:

$$3\text{-}\mathrm{SAT}{\le }_m^p\mathrm{SUBSET}\mathrm{SUM}.$$

Link to original

Weak NP-hardness

The complexity of the subset sum problem depends heavily on the numerical encoding of its input.

• Binary Encoding: When the numbers are encoded in binary, the problem is NP-hard.
• Unary Encoding: If the numbers are encoded in unary (e.g., $5$ is encoded as 11111 rather than the binary 101), the input size becomes exponentially larger, and the dynamic programming algorithm runs in time polynomial to this unary input size. Hence, under unary encoding, the problem is in P.

Problems that exhibit this specific complexity-theoretic behaviour—NP-hard in general, but solvable in polynomial time if inputs are given in unary—are called weakly NP-hard (or pseudo-polynomial).

Practical Implications

We would never actually use the unary encoding to run the algorithm in the real world. Unary encoding simply acts as a formal, simple-to-state promise: every number in the input is polynomially bounded by the input size.

Therefore, a more practical reformulation is: Subset Sum is NP-hard in general, but lies in P if every number in the input is polynomially bounded by the input size. This scenario happens surprisingly often in practice, as the numerical values frequently represent bounded quantities like physical objects.

Reductions

Reduction to Knapsack Problem

Given an instance $(P_s,W_s)$ of the subset sum problem, construct an instance $(Q_k,S_k,W_k,P_k)$ of the knapsack problem as follows:

• for each $z\in P_s$, add a pair to $Q$: $Q\leftarrow Q\cup \{(z,z)\}$
• set $W_k\leftarrow W_s$,
• set $P_k\leftarrow W_s$

Thus:

$$\begin{array}{rl}& \sum _{(w,p)\in S_k}w\le W_k\wedge \sum _{(w,p)\in S_k}p\ge P_k\\ ⟺& \sum _{z\in P_s}z\le W_s\wedge \sum _{z\in P_s}z\ge W_s\\ ⟺& \sum _{z\in P_s}z=W_s\end{array}$$

From the above, it follows that the Knapsack problem is also weakly NP-hard.

Approaches

Brute-force

A brute-force approach evaluates all possible subsets of $S$ and calculates their sum. Since there are $2^n$ possible subsets and computing the sum of a subset takes at most $O(n)$ operations, this approach is strictly exponential.

Time complexity: $O(n{2}^n)$

Dynamic Programming

The problem can be solved in pseudo-polynomial time using dynamic programming.

Let $DP[i,j]$ be a boolean value indicating whether a subset of the first $i$ elements $\{w_1,\dots ,w_i\}$ can sum to exactly $j$. The state transition is defined as:

$$DP[i,j]=\{\begin{array}{ll}DP[i-1,j]\vee DP[i-1,j-w_i]& \text{if }j\ge w_i\\ DP[i-1,j]& \text{if }j<w_i\end{array}$$

The base cases are $DP[0,0]=\text{True}$ and $DP[0,j]=\text{False}$ for $j>0$. The target sum $W$ is achievable if $DP[n,W]$ evaluates to $\text{True}$.

Time complexity: $O(nW)$

This time complexity is pseudo-polynomial because it scales linearly with the numeric magnitude of the target sum $W$, rather than polynomially with the number of bits required to represent $W$ in the input (which is $O(\log W)$ bits).