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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Try reducing from the PARTITION problem instead of general SUBSET-SUM. $\endgroup$
    – Yuval Filmus
    Jul 2, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 12:58

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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