Knowing if there are two solutions to the subset sum problem 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?
Your (self) answer is ok, but you can also build a reduction in which there is no &quot;trivial&quot; solution.
Start from $X = \{ x_{1}, \ldots, x_{n} \}, x_i &gt; 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 &quot;forced to solve&quot; 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$.