Knowing if there are two solutions to the subset sum problem

Question

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?

Answer 1

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

Answer 2

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.