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.

Improve this question
$\endgroup$
12
  • $\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
    Commented Mar 8, 2019 at 15:44
  • $\begingroup$ @Juho I see. Do you think that this problem is solvable? $\endgroup$
    – DreamConspiracy
    Commented Mar 8, 2019 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
    Commented Mar 8, 2019 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. ♦
    Commented Mar 8, 2019 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. ♦
    Commented Mar 8, 2019 at 18:45

0

Reset to default