# Proving set-partition problem is NP-complete (using reduction from subset sum)

In this post, we will prove that the set-partition problem is NP-complete using a reduction from the subset sum problem (which is NP-complete). This is also happens to be Exercise 34.5-5 in CLRS3.

We will follow the template given in an earlier post.

## Problem statement

Given a set $$S$$ of numbers, determine whether $$S$$ can be partitioned into $$A$$ and $$\overline{A} = S - A$$, such that: $\sum_{x \in A} x = \sum_{x \in \overline{A}} x$

## Showing the problem is in NP

Let $$(A, \overline{A})$$ be the certificate. We can verify the certificate in linear time by summing the elements in each set, and comparing the result.

## Showing the problem is NP-hard

We will show that the set-partition problem is NP-hard by showing:

$\text{Subset-Sum} \leq_\text{P} \text{Set-Partition}$

### Reduction

We will prove that the existence of $$T \subseteq S$$ with sum $$t \iff S' = S \cup \{s - 2t\}$$ can be partitioned into $$(A, \overline{A})$$ as described by the set-partition problem ($$s$$ being the sum of $$S$$). We note that $$S'$$ can be constructed in $$\mathcal{O}(|S|)$$ by first summing the elements in $$S$$ and then adding $$\{s - 2t\}$$ to S, which proves our reduction is performed in polynomial time.

We will now prove both directions of the biconditional separately.

### $$\exists T \implies$$ the set-partition problem on $$S'$$ has a solution

Suppose $$T$$ exists. Let $$O$$ be $$S - T$$, i.e the “out”-elements. Let $$o$$ be the sum of $$O$$. Let $$T' = T \cup {s - 2t}$$ and $$t'$$ be the sum of $$T'$$. We can now make the following observations:

\begin{aligned} o &= s - t\\ o - t &= s - 2t \qquad &\text{Difference in sum between the}~O~\text{and}~T\\ t' &= t + (s - 2t)\\ &= s - t \qquad &\text{the sums of}~T'~\text{and}~O~\text{are equal}\\ &= o \end{aligned} This proves: $\exists T \implies (T', O)~\text{is a solution to the set-partition problem on}~ S'$

### The set-partition problem on $$S'$$ has a solution $$\implies \exists T$$

Suppose an equal-sum partitioning $$(A', \overline{A'})$$ of $$S' = S \cup \{s - 2t\}$$ exists. The sum $$a$$ of each partition must then be $$\frac{s + (s -2t)}{2} = s - t$$. We consider the partition containing the element $$\{s - 2t\}$$ to be $$A'$$. Let $$A = A' - \{s - 2t\}$$. We can observe $$S' - S = \{s - 2t\} \implies A \subseteq S$$. The sum of $$A$$ is $$s - t - (s - 2t) = t$$. In other words: $$A$$ is a subset of $$S$$ with sum $$t$$, i.e. a witness to $$\exists T~\blacksquare$$