9
$\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.

Improve this question
$\endgroup$
8
  • $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 9:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.