I was reading this post, and in it I learned how to make difficult instances of the SubSet Sum Problem.

There the guy who responded to the post says that it is necessary to have density 1.0 and all elements of the difficult instance must have a size in bits equivalent to the number of elements in the vector $S$ of integers. And that the target value $x$ must ideally use around $(k / 2)$ of the values available in $S$, where $k$ is the number of elements in the vector $S$.

If the instance does not meet one of the requirements, from what I understand, there is a polynomial algorithm $A$ that solves it. I thought ok, I think it must be correct, but I found a strategy that seems to mess up the logic a little. I feel like exponentiality must be somewhere in the strategy, but I couldn't find where.

The strategy is to reformulate the problem instance into $k$ instances equivalent to the first.

For example, suppose the existence of the following instance: $$S = {128, 129, 135, 157, 169, 188, 210, 245}$$ $$x = 642$$ The answer is ${128, 135, 169, 210}$. Now let $m$ be the smallest element in $S$, that is, $m = min(S)$. In this case, $m = 128$. Now subtract each of the $k$ elements in $S$ by $(m-1)$. Resulting in $Z$: $$Z = {1, 2, 8, 30, 42, 61, 83, 118}$$ And this gives us 6 possible outputs: $$Y = {7, 134, 261, 388, 515, 642}$$ Note that the difference between each of the elements in $Y$ is $(m-1)$. I don't really know how to explain this step, but it always seems to work. And perhaps this is the most delicate part of the strategy, because for the various cases I tested, it worked well, but there may be a counterexample.

From this vector $Y$ of target values, the intention is that if there is only one answer in the original instance, then there is only one value of $Y$ such that it is reachable through the elements in $Z$. Note that the answer seems to be preserved positionally, notice that the first , third, fifth and seventh elements of $Z$ remain the answer for the instance just as they were the answer in $S$. See that the answer is confirmed when we evaluate element 134 of vector $Y$ as the target. Confirming that the instance has a solution.

The idea here is to take the original instance, assemble the $Z$ vector, assemble the $Y$ vector, and then apply a polynomial case solving algorithm to each element in $Y$ as a target (since, as we saw above, the structure of the vector was completely changed , in a way that disrespects the requirements for being a difficult instance). It is as if the method had transformed a difficult instance into approximately $k$ easy instances.

This all seems to me to be polynomial, but there really must be some counter-example in which the method makes a mistake, or perhaps the strategy only works for small cases. What do you think? Do you have any counter examples?

  • $\begingroup$ What is Y, where does that come from? $\endgroup$
    – user555045
    Commented Feb 4 at 23:42
  • $\begingroup$ @harold I basically took the original target $x$, and decremented it several times by $(m-1)$ units and saving the result of each decrement in vector $Y$, until $(m-1)$ was greater than or equal to what was left. It was a kind of hunch that has worked out in every instance I've tested it so far. I know how to build vector $Y$ for any instance, but I can't explain why it works so well. $\endgroup$
    – Edu
    Commented Feb 4 at 23:53
  • $\begingroup$ What if the second entry of S was 133? $\endgroup$
    – user555045
    Commented Feb 4 at 23:58
  • $\begingroup$ @harold very very good man, I can't believe I didn't see this before. This does not bury the method yet since, even though there are false positives, the answer always seems to be among them, but it is certainly a hole in my method. Very good man, thanks for answering. $\endgroup$
    – Edu
    Commented Feb 5 at 0:14
  • 1
    $\begingroup$ @Highheath I believed that perhaps this method could be applied iteratively, and that somehow might make the method work for large numbers as well. But I tested it here, and iteratively, it didn't work, I only managed to reduce the largest number of S by half (one bit less, that is, nothing). The method really only works if the number is small. Thanks for commenting High. 👍 $\endgroup$
    – Edu
    Commented Feb 5 at 17:25


Your Answer

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