Subset Sum Problem

Definition

Subset Sum Problem

Let be a multiset of positive integers and be a target sum. The subset sum problem is a decision problem asking whether there exists a subset such that the sum of the elements in is exactly :

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:

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., 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 of the subset sum problem, construct an instance of the knapsack problem as follows:

• for each , add a pair to :
• set ,
• set

Thus:

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 and calculates their sum. Since there are possible subsets and computing the sum of a subset takes at most operations, this approach is strictly exponential.

Time complexity:

Dynamic Programming

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

Let be a boolean value indicating whether a subset of the first elements can sum to exactly . The state transition is defined as:

The base cases are and for . The target sum is achievable if evaluates to .

Time complexity:

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