<p>This question was originally <a href="https://cs.stackexchange.com/questions/105339/subset-sum-search-problem-for-input-with-at-most-one-solution">asked on CS.se</a>. A little bit of initial discussion can be found in the comments there. </p>

<hr>

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

<hr>

<p>My thoughts: The reason I think this may be possible is because this is an <strong>extremely</strong> strong restriction on <span class="math-container">$S$</span>. 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.</p>

CC BY-SA 4.0
2019-03-09T18:23:16.020Z
Just to clarify, you want the set S to have the uniqueness property **for all** possible values of X or just for W?
Konstantinos Koiliaris
CC BY-SA 4.0
2019-03-09T18:30:19.650Z
@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)
DreamConspiracy
CC BY-SA 4.0
2019-03-09T19:06:06.080Z
The problem still feels hard to me, but maybe a careful analysis of the set's structure would prove otherwise; since all your elements are distinct natural numbers up to W and forcing the unique sum property, will make S very sparse.
Konstantinos Koiliaris
CC BY-SA 4.0
2019-03-09T19:12:27.857Z
@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.
DreamConspiracy
CC BY-SA 4.0
2019-03-09T19:15:25.993Z
You also force all elements of $S$ to be distinct ? (i.e.  can the subsets have only one element?)
Marzio De Biasi
CC BY-SA 4.0
2019-03-09T19:18:17.660Z
@MarzioDeBiasi subsets can have only one element
DreamConspiracy
CC BY-SA 4.0
2019-03-12T11:23:26.357Z
After a little bit of search: the property of $S$ is called *subset-sum distinctness* (see for example: [Integer Sets with Distinct Subset-Sums](https://www.jstor.org/stable/2007933?seq=1#page_scan_tab_contents) or [A generalization of a subset-sum-distinct sequence](https://pdfs.semanticscholar.org/34c6/92e4f72c912acd11798bb36fd8b3214d7aa3.pdf)). There is also a [conjecture by Conway-Guy](https://oeis.org/A005318). But I didn't find anything related to subset-sum.
Marzio De Biasi
CC BY-SA 4.0
2019-03-15T09:19:45.240Z
This is kind of tangential, but the paper [Dense Subset Sum may be the hardest](https://arxiv.org/pdf/1508.06019.pdf) 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.
Whosyourjay
<np-hardness><polynomial-time><promise-problems>
Subset sum problem with at most one solution for any target
DreamConspiracy
# Subset sum problem with at most one solution for any target

(Asked by: username_0 on 2019-03-09)

This question was originally [asked on CS.se](https://cs.stackexchange.com/questions/105339/subset-sum-search-problem-for-input-with-at-most-one-solution). 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.

**Tags:** np-hardness, polynomial-time, promise-problems
> **Comments:**
> **username_1**: Just to clarify, you want the set S to have the uniqueness property **for all** possible values of X or just for W?  
> **username_0**: @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)  
> **username_1**: The problem still feels hard to me, but maybe a careful analysis of the set's structure would prove otherwise; since all your elements are distinct natural numbers up to W and forcing the unique sum property, will make S very sparse.  
> **username_0**: @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.  
> **username_2**: You also force all elements of $S$ to be distinct ? (i.e.  can the subsets have only one element?)  
> **username_0**: @MarzioDeBiasi subsets can have only one element  
> **username_2**: After a little bit of search: the property of $S$ is called *subset-sum distinctness* (see for example: [Integer Sets with Distinct Subset-Sums](https://www.jstor.org/stable/2007933?seq=1#page_scan_tab_contents) or [A generalization of a subset-sum-distinct sequence](https://pdfs.semanticscholar.org/34c6/92e4f72c912acd11798bb36fd8b3214d7aa3.pdf)). There is also a [conjecture by Conway-Guy](https://oeis.org/A005318). But I didn't find anything related to subset-sum.  
> **username_3**: This is kind of tangential, but the paper [Dense Subset Sum may be the hardest](https://arxiv.org/pdf/1508.06019.pdf) 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.  

---

## 0 answers

