2
$\begingroup$

Given the following NP-complete problem:

PARTITION

Input: A list of positive integers $a_1, a_2, \dots, a_n$.

Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such that the sum of each part is the same?

Now I want to reduce PARTITION to the following problem:

TRIPLE-SUM

Input: A list of positive integers $a_1, a_2, \dots, a_n$.

Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such that the sum of the numbers in $A_1$ is exactly three times the sum of the numbers in $A_2$?

I'm struggling to see how the transformation can take place. I've tried transforming the list $a_1, a_2, \dots, a_n$ by multiplying each element by $3$ (stupid... I know...) but everything I tried failed. Is there a way to perform this reduction? Does it even require to modify the input list?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Perhaps you should spend a few more days on this problem. Reductions can be tricky. You might want to take a look at the related problem of SUBSET-SUM. $\endgroup$ – Yuval Filmus Apr 16 '16 at 22:42
  • 2
    $\begingroup$ I think there is a way to do the reduction by adding an additional number to the input. Just a single number. Maybe i'm telling you too much… $\endgroup$ – rotia Apr 18 '16 at 15:13
  • $\begingroup$ @rotia: Clever. I figured out a much more complicated way that worked by adding n numbers very close to the original ones... $\endgroup$ – gnasher729 Oct 25 '16 at 17:54
  • $\begingroup$ Our reference question may provide some inspiration. $\endgroup$ – Raphael♦ Oct 25 '16 at 22:12
  • $\begingroup$ @rotia Hmm, that makes me think - can we reduce PARTITION to DOUBLE-SUM? (Trying to add The Number in this case does not work) $\endgroup$ – MCT Oct 26 '16 at 1:39

Your Answer

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

Browse other questions tagged or ask your own question.