# Subset Sum Search Problem for Input with At Most One Solution [closed]

Edit: This question has been reasked on TCS.

We first consider the search version of the subset sum problem: Given a set $$S$$ of $$n$$ naturals, find a subset of $$S$$ that sums to exactly $$W$$. My question concerns this problem, with an additional restriction on set $$S$$: For all possible values of $$X$$, there exists at most one subset that sums to $$X$$ (in other words, no two subsets of $$S$$ sum to the same value). Can we find a polynomial time algorithm for this problem given this restriction?

My thoughts: The reason I think this may be possible is because this is an extremely strong restriction on $$S$$. Most sets are very far from having this property. The construction of an algorithm would likely begin with a strong characterization of the sets that even have this property, and work from there. However, I'm having trouble proving strong theorems about the sets that obey this restriction.

• Problems with such guarantees are known as promise problems. Sometimes these promises don't help (for example, it's hard to find a Hamiltonian cycle even if we know it exists) but sometimes they do (for example, you can find a satisfying assignment for $n$-variable SAT if the formula has at least $2^n/n$ satisfying assignments). – Juho Mar 8 at 15:44
• @Juho I see. Do you think that this problem is solvable? – DreamConspiracy Mar 8 at 15:48
• No, I think it's hard in the following sense. UNIQUE-SAT is SAT with a unique solution, and the problem is $D^P$-complete (yes, see here). Now, I guess all you need is a parsimonious reduction from SAT to SUBSET SUM and you are done. I think this is just a matter of putting the pieces together carefully. – Juho Mar 8 at 15:52
• If you take $n$ random integers, each $n^2$ bits long, then it will satisfy your restriction. I don't know whether the subset sum problem is expected to be hard on that distribution. – D.W. Mar 8 at 18:43
• @Juho, I think that argument would work if the promise was that there is a unique solution (there is a unique subset that sums to the target). But here we have a stronger promise regarding the set $S$: for all other possible targets, it's also true that there is at most one subset that sums to them. I don't see how to make the UNIQUE-SAT ideas apply given this stronger promise. – D.W. Mar 8 at 18:45