0
$\begingroup$

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!

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Just going to write this out to make sure I'm fully grasping things: S can be partitioned into A and B such that the sums of their respective elements are equal if an only if there exists a subset S prime of S where S prime is half of S. This is because if A and B's sums equal each other, and together make up the total sum of S, then they both must be half of S. That right? If that is correct, I think the only thing that confuses me is "The claim follows by picking S = A". What does this mean? $\endgroup$ – drewm1192 Apr 28 '20 at 0:54
  • $\begingroup$ That's right! And "The claim follows by picking S = A" is a typo. It should be $S'$. I have edited my answer. $\endgroup$ – Steven Apr 28 '20 at 1:18
  • $\begingroup$ Ah okay, thank you very much Steven. Now maybe this next comment is a bit of a leap, but here it goes: for the subset sum problem we give a set and a target value as inputs. To reduce that problem to this partition problem, we could essentially say our inputs to the subset sum problem are 1) Our total set S and 2) our target value of 1/2 the sum of the elements in S. By doing this, we could verify if there is a subset sum of 1/2 the total sum of all the elements in the set (call this set of elements A), and if there is, the remaining elements form the other subset (B) that is of equal sum. $\endgroup$ – drewm1192 Apr 28 '20 at 1:35
  • $\begingroup$ Be careful because the original subset sum instance might have a target value that is not half the sum of the elements in its input set $S$. To complete the reduction you need to show how to transform the original instance into an equivalent instance of subset sum with some input set $\overline{S}$ and for which the target value is exactly $\frac{1}{2} \sum_{x \in \overline{S}} x$. This latter instance is exactly an instance of partition, therefore this would immediately show that partition is $\mathsf{NP}$-hard. See the second part of my answer for how to do this. $\endgroup$ – Steven Apr 28 '20 at 2:12
  • $\begingroup$ Awesome, that makes sense. Thanks a million, Steven. You are a saint. $\endgroup$ – drewm1192 Apr 28 '20 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.