0
$\begingroup$

Here's a statement of the set partition problem:

The set partition problem takes as input a set $S = \{ a_1, a_2, ..., a_n \}$(all positive integers). Can $S$ be partitioned into two sets $A$ and $B$ such that the sum of the numbers in $A$ is equal to the sum of the numbers in $B$?

Here's a statement of a variation of the set partition problem:

Given an input set $S = \{ a_1, a_2, ..., a_n \}$ (all positive integers), can you partition $S$ into $A$ and $B$ such that $| \sum_{i \in A} a_i - \sum_{i \in B} a_i| < 1000$?

My goal is to show that the variation is NP-complete by reducing the set partition problem to the variation, and here's what I've tried:

  1. Given an instance of the set partition, $S$, let the total sum of its elements be $s$, then create a set $S \cup \{ s + 1000, s \}$ as an instance for the variation. But this doesn't seem to do the trick.
  2. Given an instance of the set partition, $S$, do something to the elements in $S$ (for example, multiply by 2, subtract by 1000). This path feels promising but I'm again stuck.
$\endgroup$
1
$\begingroup$

Thanks to D.W.'s generous help, I managed to figure it out. Given an instance of the Partition problem, $S$, we can just scale every element in $S$ by 1000, and the new $S'$ becomes an instance of the variation. Then the reduction mapping holds, because scaling increases the difference between numbers. If $S$ is a YES instance, $S'$ can also be partitioned into two sets with equal sum, but if $S$ is a NO instance, all of the possible partitions of $S'$ must have difference $\geq 1000$. The reduction is clearly polynomial, and the variation is clearly in NP, so proof is complete.

$\endgroup$
0
$\begingroup$

Hint:

If $k$ is an integer and $|1000k| < 1000$, then what can you conclude about $k$? How could that be useful?

$\endgroup$
1
  • $\begingroup$ Thank you very much for this useful hint! I managed to figure it out! $\endgroup$ – Yi Qin Dec 4 '20 at 21:49

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.