0
$\begingroup$

I'd like to prove that the following problem is NP-complete. I'd just like to know what reduction I should do:

Two Subset Sum: Given a set S of integers and an integer T, determine whether there are two subsets of S such that the sum of the numbers of one is T and the other is 2T. The subsets do NOT have to be disjoint.

And I want to use the classic subset problem to prove this:

Subset Sum: Given a set S of integers and an integer T, determine whether there is a subset of S such that the sum of the numbers is T.

I'm slightly struggling with the reduction from Subset-Sum to 2-Subset-Sum, as simply adding to the set the double of each number and using the same T does not work, e.g S = {1,7,8,5} and S'={1,2,5,10,7,8,14,16} with T = 10 wouldn't work, as S' would return "true" and S should return "false".

Thank you.

$\endgroup$
  • $\begingroup$ Try reducing from the PARTITION problem instead of general SUBSET-SUM. $\endgroup$ – Yuval Filmus Jul 2 '17 at 9:27
  • $\begingroup$ It might be easier with the Partition problem, but I specifically want from Subset-Sum (It's part of the question's requirement). $\endgroup$ – BAM Jul 2 '17 at 9:39
  • $\begingroup$ In that case, you can compose the reduction from Subset-Sum to Partition and the reduction from Partition to your problem. Both are pretty simple. $\endgroup$ – Yuval Filmus Jul 2 '17 at 10:23
  • $\begingroup$ Ok, thanks. Do you have an idea how to do the reduction directly though? It's definitely possible. $\endgroup$ – BAM Jul 2 '17 at 11:28
  • $\begingroup$ Think about how you could reduce a problem in which you are given a set $S$ of integers and an integer $T$, and need to determine whether some subset of $S$ sums to $T$, to the same problem, but with $T$ forced to be 0. When constructing the instance of the second problem, think about what effect multiplying all numbers, or adding a constant to each number, has on its solutions. $\endgroup$ – j_random_hacker Jul 2 '17 at 12:58
1
$\begingroup$

There is a trivial reduction from Partition to your problem: given an instance $S$ of partition, construct the instance $(S,\frac{1}{2} \sum_{i \in S} i)$ of your problem. This shows that if you take any reduction from Subset-Sum to Partition, you immediately get a reduction from Subset-Sum to your problem. You can find the reduction from Subset-Sum to Partition in many places, or come up with it on your own.

$\endgroup$

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.