8
$\begingroup$

This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there.


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$ Just to clarify, you want the set S to have the uniqueness property for all possible values of X or just for W? $\endgroup$ – Konstantinos Koiliaris Mar 9 at 18:23
  • $\begingroup$ @KonstantinosKoiliaris all possible values of $X$. This is also the reason that a reduction to unique SAT probably won't work (as was discussed in the CS.se thread) $\endgroup$ – DreamConspiracy Mar 9 at 18:30
  • 1
    $\begingroup$ @KonstantinosKoiliaris yes. I'm not even convinced that we can't show this to be trivially polytime by arguing that $S$ has to be so sparse that traditional algorithms (DP) work. I haven't been able to find any literature about the asymptotic maximum size of $S$ given $W$ though. But maybe I'm just searching for the wrong thing. $\endgroup$ – DreamConspiracy Mar 9 at 19:12
  • 1
    $\begingroup$ After a little bit of search: the property of $S$ is called subset-sum distinctness (see for example: Integer Sets with Distinct Subset-Sums or A generalization of a subset-sum-distinct sequence). There is also a conjecture by Conway-Guy. But I didn't find anything related to subset-sum. $\endgroup$ – Marzio De Biasi Mar 12 at 11:23
  • 2
    $\begingroup$ This is kind of tangential, but the paper Dense Subset Sum may be the hardest considers cases where few subsets sum to any $X$. If you try their Lemma 3.1 with your unique sum property you get a $2^{0.406 n}$ algorithm. $\endgroup$ – Whosyourjay Mar 15 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.