The Partition Problem: Reducing to prove NP-Completeness

Question

I am struggling with the below problem. Curious to hear any guidance.

---

The Partition Problem is the following:

$\textbf{Instance:}$ A multiset of numbers $S = \{a_1, a_2, \ldots , a_n \}$.

$\textbf{Question:}$ Can $S$ be partitioned into two multisets $A$ and $B$ such that the sum of the numbers in $A$ is equal to the sum of the numbers in $B$?

Prove that the Partition Problem is NP-complete.

---

Things I could reduce from that I know of are 3-SAT, Vertex Cover, Subset Sum, Independent Set, and the clique problem. My assumption is that I should be reducing from the Subset Sum problem, but I struggle with that problem as well.

Is anyone able to help shed some light on this? Also, any explanation in plain English (maybe with some notation) would be greatly appreciated as I'm struggling with the concepts here. Just mathematical notation alone might make it more difficult for me to understand at the moment.

Thank you in advance!

Answer 1

Partition is equivalent to a special case of the subset-sum problem: $S$ can be partitioned into two sets $A$ and $B$ such that $\sum_{x \in A} x = \sum_{x \in B} x$ if and only if $\exists S' \subseteq S$ such that $\sum_{x\in S'} x = \frac{1}{2}\sum_{x \in S}x$.

Proof of $\implies$: Given $A$ and $B$ that partition $S$ and are such that $\sum_{x \in A} x = \sum_{x \in B}$ you must have $\sum_{x \in S}x =\sum_{x \in A} x + \sum_{x \in B} x = 2 \sum_{x \in A} x \implies \sum_{x \in A} x = \frac{1}{2}\sum_{x \in S}x$. The claim follows by picking $S' = A$.

Proof of $\Longleftarrow$: Given $S' \subseteq S$ such that $\sum_{x\in S'} = \frac{1}{2}\sum_{x \in S}x$ you must have $\sum_{x\in S \setminus S'} x = \sum_{x \in S}x - \sum_{x \in S'}x = \frac{1}{2}\sum_{x \in S}x$. The claim follows by picking $A=S'$ and $B = S \setminus S'$.

---

To show that this special case of subset sum (i.e. partition) is in $\mathsf{NP}$ notice that a subset $S' \subset S$ such that $\sum_{x \in S'} x = \frac{1}{2}\sum_{x \in S}$ is a yes-certificate.

To see that this special case of subset sum is still $\mathsf{NP}$-hard consider an instance $\langle S, T \rangle$ of subset sum where $S$ is a (multi-)set and $T$ is the target value. Let $M = \sum_{x \in S} x$.

Create a new instance subset sum $\langle \overline{S}, \overline{T} \rangle$ where $\overline{S} = S \cup \{ M-2T \}$ and $\overline{T}=M-T$.

If there is a solution $S' \subseteq \overline{S}$ to $\langle \overline{S}, \overline{T} \rangle$ then $\sum_{x \in S'} x = \sum_{x \in \overline{S} \setminus S'} x= M-T$ (since the sum of the elements in $\overline{S}$ is $2(M-T)$). At least one of $S'$ and $\overline{S} \setminus S'$ contains element $M-2T$, call this set $S^*$. Then the $S^* \setminus \{M-2T\}$ is a subset of $S$ and the sum of its elements is $(M-T)-(M-2T)=T$, showing that the original instance $\langle S, T \rangle$ is a yes instance.

On the other hand, if there is a solution $S' \subseteq S$ to $\langle S, T \rangle$, then the set $S' \cup \{ M-2T \}$ is a subset of $\overline{S}$ and the sum of it's elements is $T + (M - 2T) = M-T = \overline{T}$, showing that $\langle \overline{S}, \overline{T} \rangle$ is a yes instance. This concludes the proof.