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$

closed as off-topic by D.W. Mar 9 at 20:04

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

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