0
$\begingroup$

I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are at least two or more solutions.

My thought is that potentially it is FNP, because the Another Solution Problem (ASP) for Subset Sum appears to be FNP (by reduction from 3SAT), but ASP assumes that at least one solution was already found. Is there a way to say something about the hardness of finding two solutions without prefacing that one was already found?

$\endgroup$
2
$\begingroup$

Your (self) answer is ok, but you can also build a reduction in which there is no "trivial" solution.

Start from $X = \{ x_{1}, \ldots, x_{n} \}, x_i > 0$ with target sum $K$ and build:

$X' = \{ 8 * x_{1}, \ldots, 8 * x_{n} \} \cup \{ 1, 1, 2 \}$ and target sum $K' = 8*K + 2$

In this case in order to solve the new problem $\langle X', K' \rangle$ you are "forced to solve" the original one, and there are at least two solutions to $\langle X', K' \rangle$ if there is a solution to $\langle X, K \rangle$.

$\endgroup$
3
  • $\begingroup$ It seems to me like you should use $ \{ 1, 1 \} $ and $ K' = 8 * K + 2 $ so that if there is a solution to the original problem, it becomes two in the new one. In this formulation, it looks to me like there is the same number of solutions and you have to pick $ 2 $ every time. $\endgroup$ – user73236 Jan 8 at 16:39
  • $\begingroup$ Sorry, I meant $ K' = 8 * K + 1 $. $\endgroup$ – user73236 Jan 8 at 17:05
  • 1
    $\begingroup$ @user73236 in your version there is no distinction between the two $1$s so the solution counts as one. And also in my answer an original solution $Y$ becomes two: $Y \cup \{1,1\}$ and $Y \cup \{2\}$ $\endgroup$ – Marzio De Biasi Jan 8 at 17:52
1
$\begingroup$

Yes, this appears to be true in the case that the integers are all positive. We simply take a Subset Sum instance defined by the set $ X = \{ x_{1}, \ldots, x_{n} \} $ and the target value $ K $ and create the set $ X' = X + \{ K \} $. Then there are at least two solutions to this problem if there is at least one to the original. Likewise, if there are two solutions given to this At Least Two Subset Sum problem; we simply pick either of them unless one of them is $ \{ K \} $, in which case we simply pick the other solution. Any solution to the At Least Two Subset Sum problem besides $ \{ K \} $ cannot have $ \{ K \} $ as a subset since $ K + \sum_{ s \in S } s > K $ because all $ s $ are positive. So the other solution must solve the original problem.

$\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.