SUBSET-SUM ≤p PARTITION | Complexity Atlas

The construction

The derivation — the part not to skip. $\mathrm{SUBSET\text{-}SUM}$ has an external target $S$ ; $\mathrm{PARTITION}$ has none — its target is dictated from within and is necessarily half the total. The reduction must "bake the $S$ in".

Write $T=\sum_i a_i$ . Suppose for a moment — purely to think, not as part of the algorithm — that some $I$ has $\sum_{i\in I}a_i=S$ . The other side sums to $T-S$ . Add an element $b$ to the "small" side. In the case $S>T/2$ we require $\sum_{i\in I}a_i=S$ and $\sum_{i\notin I}a_i+b=S$ , whence $b=S-\Bigl(\underbrace{\textstyle\sum_i a_i}_{=T}-\underbrace{\textstyle\sum_{i\in I}a_i}_{=S}\Bigr)=2S-T .$

And here is the beauty. The middle expression $S-\sum_{i\notin I}a_i$ is not computable by the reduction: it depends on $I$ , which is exactly the object we do not have. But the final expression $2S-T$ depends only on the input — $S$ is given and $T$ takes linear time. The intermediate question moved from "depends on the solution" to "depends on the input", and with that the reduction became legal. Symmetrically, if $S<T/2$ we get $b=T-2S$ .

Algorithm $R$ . On input $(a_1,\dots,a_n,S)$ :

Compute $T\leftarrow\sum_i a_i$ .
If $2S=T$ : return $(a_1,\dots,a_n)$ unchanged.
If $2S>T$ : return $(a_1,\dots,a_n,\,2S-T)$ .
If $2S<T$ : return $(a_1,\dots,a_n,\,T-2S)$ .

The comparison is written as $2S$ against $T$ rather than $S$ against $\tfrac12T$ so as to stay in the integers when $T$ is odd; it is the same comparison. When $T$ is odd, case 2 simply cannot occur. In the other two cases $b>0$ strictly, precisely because of the case condition.

Visualization

A = {3, 5, 6, 11}T = 14

Original number

Correctness — both directions

SUBSET-SUM ∈ ⟹ PARTITION ∈

Suppose $(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}$ ; some $I$ has $\sum_{i\in I}a_i=S$ . Split by the case the algorithm took.

Case $2S=T$ . The output is $(a_1,\dots,a_n)$ . The set $I$ satisfies $\sum_{i\in I}a_i=S=T/2$ , so $\sum_{i\notin I}a_i=T-T/2=T/2$ — the two sides are equal, and the output is in $\mathrm{PARTITION}$ .

Case $2S>T$ . The output is $(a_1,\dots,a_n,b)$ with $b=2S-T>0$ and total $T+b=2S$ . Take the side $I$ itself: $\sum_{i\in I}a_i=S=\tfrac12(2S)$ — exactly half the new total. So the output is in $\mathrm{PARTITION}$ . (The other side is $\{a_i\}_{i\notin I}$ together with $b$ , summing to $(T-S)+(2S-T)=S$ .)

Case $2S<T$ . The output is $(a_1,\dots,a_n,b)$ with $b=T-2S>0$ and total $T+b=2T-2S$ . Take the side $I\cup\{b\}$ : it sums to $S+(T-2S)=T-S=\tfrac12(2T-2S)$ — exactly half. So the output is in $\mathrm{PARTITION}$ .

PARTITION ∈ ⟹ SUBSET-SUM ∈

Suppose the output is in $\mathrm{PARTITION}$ ; it splits into two sides of equal sum. Split by case again.

Case $2S=T$ . The output is the original input, and an equal split means some $I$ has $\sum_{i\in I}a_i=T/2=S$ . So $(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}$ .

Case $2S>T$ . The output totals $2S$ , so each side sums to $S$ . Consider the side not containing the padding element $b$ (exactly one of the two sides contains it). That side consists solely of original elements; let $I$ index them. Then $\sum_{i\in I}a_i=S$ , so $(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}$ .

Case $2S<T$ . The output totals $2T-2S$ , so each side sums to $T-S$ . Consider the side that does contain $b=T-2S$ , and let $J$ index its original elements. Then $\sum_{i\in J}a_i+(T-2S)=T-S\quad\Longrightarrow\quad\sum_{i\in J}a_i=S .$ So $(a_1,\dots,a_n,S)\in\mathrm{SUBSET\text{-}SUM}$ .

In all three cases we obtained a subset of the original elements summing to $S$ , as required.

Cost of the reduction

TimeO(|x|²)

SpaceO(|x|)

Output sizeO(|x|)

Let $m$ be the longest encoding among $a_1,\dots,a_n,S$ , and $|x|\ge n+m$ the input size. Step 1 performs $n-1$ additions; each partial sum is at most $n\cdot10^m$ , so of length $\le m+\lceil\log_{10}n\rceil+1$ , and one addition is linear in the lengths — $O(n(m+\log n))=O(|x|^2)$ overall. Steps 2–4 are a single comparison and subtraction.

Running time is measured in encoding length, not in the numbers' values: had we needed to count up to $T$ , the reduction would not be polynomial. The output length is $O(|x|)$ — which matters for transitivity, since a reduction that inflates its input exponentially is useless under composition.

What it buys

$\mathrm{PARTITION}$ is NP-hard, and lies in $\mathrm{NP}$ , hence NP-complete. From there the chain continues to $\mathrm{BIN\text{-}PACKING}$ .

Pitfalls

Why from $\mathrm{SUBSET\text{-}SUM}$ rather than $\mathrm{SAT}$ . $\mathrm{SAT}$ would also work — any NP-complete problem reduces to any other — but "encoding a formula as a set of numbers" is wasted labour. The principle: move between problems in the same world. Here numbers go in and numbers come out.
The algorithm computes $T$ and compares — that is allowed. What it does not do is test whether a subset summing to $S$ exists, and it cannot. The element $a_{n+1}$ helps decide nothing; it only guarantees "if there was a solution before, there is one now, and conversely".
The output is a list of $n+1$ numbers, not a pair (numbers, target). That is exactly what a $\mathrm{PARTITION}$ input is; nobody promised $n$ would stay fixed.

The chain

Rests on

VC ≤p SUBSET-SUM

Used later by

PARTITION ≤p BIN-PACKING

Where this was read from

Lesson 12משפט 2 (לב השיעור): $\mathrm{SUBSET\text{-}SUM} \le_p \mathrm{PARTITION}$
Guided exercisepartition-from-subset-sum
2026 '1 מועד 2 $Subset\text{-}Sum$ against $Partition$ , and the reduction between them.
2025 '2 מועד 1Defining $Partition$ in decimal representation and proving it hard.