1
$\begingroup$

For brevity, let $s(D) = \sum_{d\in D} d$ denote the sum of the elements in $D$.

Given a set $A = \{a_1, \dots, a_n\}$ of positive integers, and a target value $K$, the subset sum problem is to determine if there exists a subset $A' \subseteq A$ such that $s(A') = K$.

Given a set $B = \{b_1, \dots, b_m\}$ of positive integers, the partition problem is to determine if there exists a subset $B' \subseteq B$ such that $s(B') = s(B \setminus B')$.

Theorem. Subset sum $\propto$ partition.

The proof found in most references, and the one given in the relevant CS SE question, performs the reduction from subset to partition by letting $S = s(A)$ and taking $B = A \cup \{S + K, 2S - K\}$ in the reduction.

I came up with the following alternative approach.


Proof. Given an instance of subset sum, take $S = s(A)$ and construct an instance of the partition problem with $B = A \cup \{S, 2K\}$.

Suppose that $B$ admits a partition $B' \subseteq B$. Because $2K + S > s(A)$, we must have either $2K \in B'$ and $S \in B \setminus B'$ or vice-versa. Assume (without loss of generality) that the former is the case.

Now, let $A' = A \cap (B \setminus B')$ denote the elements of $A$ that are not in $B'$. We know that $$\begin{align} &&s(B') &= s(B \setminus B') \\ \iff\quad&& 2K + s(A\setminus A') &= S + s(A') \\ \iff\quad&& 2K + s(A\setminus A') + s(A') &= S + s(A') + s(A') \\ \iff\quad&& 2K + S &= S + 2s(A') \\ \iff\quad&& K &= s(A') \\ \end{align}$$

Conversely, if $A$ admits a subset having $s(A') = K$, then it is easy to see that $B' = \{2K\}\cup (A\setminus A')$ is a valid partition for $B$.


Is this proof correct?

$\endgroup$
2
  • $\begingroup$ The point of a mathematical proof is that you don't need anybody else to verify it. Mathematical truth ideally stems not from community validation, but from unequivocal proof. (In practice, proofs are typically not written in enough detail to guarantee their correctness, though proof assistants hope to fill this gap.) $\endgroup$ Commented Nov 22, 2021 at 7:41
  • $\begingroup$ @YuvalFilmus I respectfully disagree. It is a healthy habit to doubt one's intuitions and seek constructive feedback, especially when learning a new skill. $\endgroup$
    – Max
    Commented Nov 22, 2021 at 8:56

1 Answer 1

1
$\begingroup$

Yes, but perhaps more cumbersome than necessary, and less readable than it could be. Here's an alternative approach:

Let $S = \{e_1, ..., e_n\} , W \in \mathbb{N}$ be the instance for subset sum and let $$U = S \cup \left\{ \sum S , 2W \right\}$$ be the instance for partition.

Since, as you noted, $\sum S + 2W > \sum S$, we can assume that if $A$ and $B$ partitions $U$ in equal sums, $\sum S \in A$ and $2W \notin A$.

Now, $$ \sum A = \sum B = \sum U /2 = \frac{\sum S + \sum S + 2W}{2} = \sum S + W.$$

But since $\sum S \in A$, it follows that $\sum A - \sum S = W$, which is precisely the set we are looking for in subset sum.

You also need to prove that a yes instance for subset sum translates to a yes instance for partition, but that is straightforward.

$\endgroup$
4
  • $\begingroup$ Thank you for the response. I am not sure I like the notation $\sum S$ for $\sum_{s\in S} s$. It's a little bit like saying $ \{1, 2, 3\} = 1 + 2 + 3$, no? $\endgroup$
    – Max
    Commented Nov 22, 2021 at 8:59
  • $\begingroup$ But indeed $\sum \{1, 2, 3\} = 1 + 2 + 3$, no? $\endgroup$
    – Pål GD
    Commented Nov 22, 2021 at 11:41
  • $\begingroup$ If you define it that way, then sure. To me, $\sum\{1, 2, 3\} =\{1, 2, 3\}$, for the same reason that $\sum_{i=1}^1 2 = 2$. Perhaps your notation is standard but simply uncommon in my field. It sure would be nice to have a standard, short way to express this. $\endgroup$
    – Max
    Commented Nov 22, 2021 at 12:07
  • 1
    $\begingroup$ Fair enough. It's not really standard, but I've seen it in use, both with the summation sign as well as the (big) union and (big) intersection... I just find $\sum_{s \in S}s$ to be annoyingly repetitive. $\endgroup$
    – Pål GD
    Commented Nov 22, 2021 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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