-2

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,14,16} with T = 10 wouldn't work, as S' would return "true" and S should return "false".

Thank you.

BAM
  • 433
  • 1
  • 7
  • 17

1 Answers1

0

Let $\sum S$ denote the sum of the elements in a set S and let $s= \sum S_1$.
Given an instance of $SubsetSum(S_1, T_1)$ construct an instance of $TwoSubsetSum(S_2, T_2)$ by setting $S_2 = S_1 \cup \{s-2T_1\}$ and $T_2 = s-T_1$

$SubsetSum(S_1, T_1) \Rightarrow TwoSubsetSum(S_2, T_2)$
$\quad$Suppose there exists $x \subseteq S_1$ such that $\sum x = T_1$
$\quad$Then $(S_1 - x) \subseteq S_2$ such that $\sum (S_1-x)=s-T_1$ and $S_2 \subseteq S_2$ such that $\sum S_2=2(s-T_1)$

$TwoSubsetSum(S_2, T_2) \Rightarrow SubsetSum(S_1, T_1)$
$\quad$Suppose there exists $x, y \in S_2$ such that $\sum x=s-T_1$ and $\sum y = 2(s-T_1)$
$\quad$If $(s-2T_1) \in x$, then $(x - \{s-2T_1\}) \subseteq S_1$ with $\sum(x - \{s-2T_1\})=T_1$
$\quad$If $(s-2T_1) \notin x$, then $x \subseteq S_1$ with $\sum x=T_1$
$\quad$In either case, there is a subset of $S_1$ such that the sum of the numbers is $T_1$

user137481
  • 2,605