4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Juho Mar 8 at 15:44
  • $\begingroup$ @Juho I see. Do you think that this problem is solvable? $\endgroup$ – DreamConspiracy Mar 8 at 15:48
  • $\begingroup$ 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. $\endgroup$ – Juho Mar 8 at 15:52
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 8 at 18:43
  • $\begingroup$ @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. $\endgroup$ – D.W. Mar 8 at 18:45