1
$\begingroup$

I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively.
I'm measuring its performance by the average amount of time taken per subset found.

However, I suspect it may be faster than existing solvers in "near-worst" cases, but I don't know how to check this.
What are some concrete examples of near-worst-case subset-sum problems I can try it on?

Note that I'm looking for reasonable examples here (< 64 bits -- i.e., numbers that actually pop up in the real world), not, for example, an instance with 500 digits. I'm looking for reasonable examples here. The idea is that I'm trying to solve real-world subset-sum problems well in "hard" cases.

$\endgroup$
  • $\begingroup$ @user13972: Interesting, thanks! So do hard instances actually arise in the real world directly, given that we don't really deal with huge numbers in reality? ("directly" as opposed to "via a reduction of another NP-hard problem") $\endgroup$ – Mehrdad Oct 10 '17 at 7:49
4
+25
$\begingroup$

The naive dynamic programming complexity is $O(sN)$ where $s$ is the integer bit precision, $N$ is the set cardinality. With some slight tricks in memoization cutting the precision constant in half, an instance with 64 bits precision should be solvable without much optimization in a linearly increasing fashion and as fast as memory access allows.

However, the naive method for small $s$ but large $N$ is dynamic programming which has subjectively large memory requirements. In practice this is the constraint that is prohibative for large instances skewed towards small precision, since many of the non-cryptographic applications I can think of deal with embedded systems having low memory and real-time constraints that limit non-uniform memory access.

At the other end of the spectrum if you have PiB subset-sum instances with small $s$ but very large $N$, the same issues arise as in sorting. These instances are incredibly 'easy' from a theory perspective but the micromanagement constant factor details dominate such as cache usage, memory walls, parallelization, bandwidth saturation, and code/data locality. Many of the techniques for fast solvers become invalidated at that size due to either reliance on a central memoization table or chaotic memory access.

The major applications for subset-sum that I know of are cryptographic in nature, which necessitates that the natural 'real-world' integer precision is far larger than 64 bits. In addition, most of the various manufacturing and finance applications do encounter the need for integer precision much larger than 64 bits as a way to actually encode the problem without blowing up $N$ in a very non-linear manner. This is required even though the original 'real-world' quantities are far less than 64 bits.

So hard subset-sum instances with 64 bit precision don't exist in the manner that I think you want to test. If an analogy helps, this is similar a complexity outcome to finding the prime factorization of a very large number but limited to prime factors with 64 bits of precision rather than the general case.

$\endgroup$
  • $\begingroup$ +1 however, could you clarify what "s" is here? Is it the bit precision of the numbers in the set, or the bit precision of the target sum? I'm asking because choosing the target sum to be larger than the sum of all the positive numbers in the set would clearly be trivial to solve, so I don't see how it could be O(sN) if s represents the bits in the target sum. Also, are you making any hidden assumptions here? e.g. that numbers are nonnegative? Or that backtracking is disallowed? You seem to assume DP throughout which is affected by s but it's not clear to me that backtracking is affect by s. $\endgroup$ – Mehrdad Oct 11 '17 at 0:10
  • $\begingroup$ (or to put it another way, it's not clear to me that increasing s itself makes the problem immensely harder, only that it makes the pseudopolynomial-time algorithm suffer. I suppose there's a complexity theorem that you're assuming in making this argument, which would be helpful if you could clarify.) $\endgroup$ – Mehrdad Oct 11 '17 at 0:21
  • $\begingroup$ Right, I understand the claim regarding < 64-bits being easy. What I'm trying to make sense of is the rest of your answer, i.e. why I should expect much larger numbers to make the problem noticeably harder (obviously assuming constant-time arithmetic). For example, finding a subset of (say) {1000000, 1000001, 1000002} that adds up to 2000001 is no harder than finding a subset of {0,1,2} that adds up to 1... unless you restrict yourself to a pseudopolynomial-time algorithm. (But why would you?) Naively, it seems that the only thing s does is to enable larger N, so why is s itself significant? $\endgroup$ – Mehrdad Oct 11 '17 at 12:04
2
$\begingroup$

It's not clear how to formally define worst-case (or near-worst-case) instances, but here is something you could try.

The idea is to combine the following two tidbits:

  1. We know some hard instances for 3SAT.
  2. There is a reduction from 3SAT to SUBSET-SUM.

The hard instances for 3SAT are random instances at the correct clause density, which is just below the satisfiability threshold (4.2667). Applying the NP-hardness reduction that shows that SUBSET-SUM is NP-hard should result in hard instances for SUBSET-SUM.

Unfortunately, these instances are probably very large, so these instances might be too hard.

$\endgroup$
  • $\begingroup$ Yeah, I did some Googling and it seems like these examples would be ridiculously hard and not actually indicators of real-world worst-case examples. For what it's worth, I'm assuming the numbers are realistic (<= 64 bits, like most numbers that pop up in the real world) so I'm trying to benchmark it with something reasonable. $\endgroup$ – Mehrdad Oct 9 '17 at 19:40
  • $\begingroup$ Satisfiability threshold is not sufficient to make worst case of 3SAT. No pure literals, no easy resolutions, etc. Maybe, variables should be distributed uniformly? Also, we would want to make sure, that decomposition won't work on given function. $\endgroup$ – rus9384 Oct 10 '17 at 14:45
  • $\begingroup$ @rus9384 Actually, it is conjectured that SAT should be difficult even slightly before the satisfiability threshold. Of course, all this only holds with high probability for a random instance. This takes care of your uniform distribution requirement, for example. $\endgroup$ – Yuval Filmus Oct 10 '17 at 15:39
1
$\begingroup$

Not actually an answer to my own question, but if no one finds one, I think it would support what the author of this paper had to say, especially given that my own code was backtracking-based:

The empirical results in [Figure 4] do not necessarily reflect worst-case analytical results. Backtracking is better than DP for all problem instances, even as the density of the problem instance is increasing. The worst-case analyses lead to the expectation that DP will be better than BT for high-density problem instances. Apparently, the density never gets high enough to give DP the advantage. Of course, we need to keep in mind that the empirical data from randomly generated instances is an illustration of average-case complexity, not worst-case complexity. While it is not known that average time complexity differs from worst-case time complexity for either backtracking or dynamic programming, it is known that many algorithms perform far better than worst-case for instances outside the critical region.

In other words, it seems that it's hard to find hard instances of subset-sum!
And I have no idea whether it's been done at all.

$\endgroup$
1
$\begingroup$

I'll share what I learned after reading many papers about the subset sum problem, I too implemented a solver and was looking time ago to understand what a 'hard instance' really is (in regards to this problem), and what I'm going to describe worked very well as a test bench for my solver, I personally never tackled the backtracking algorithm so you might need to reconcile this information with BT dynamics, but on the other hand, this way to build up instances are effective for both DP and the 'meet-in-the-middle' approach.

In relationship to subset sum problem, the existing literature, defines usually a hard instance as a random set of equally distributed values across the problem space with $density \approx 1$ (I found a paper settling, after some analysis that in fact the hardest instances have a $density \approx 1.03$ but is not a big of a difference form the practical point of view, that is what it looks you are interested)

Assuming $N$ being the number of elements and $P$ the number of bits for encoding the maximum possible value in your set, to achieve a $density \approx 1$ you must set the same value for $N$ and $P$ as $density=N/P$

For example, as you are constraining the integers resolution to no more than 64 bits, then, $N=P=64$.

Now you need to pick 64 uniquely random values equally distributed between $1..2^{64}$, trying to really equally distribute them (not clustering near-values). This will be your input set.

Then, you need to pick the target value, for this, you must select, again, randomly, unique values from your set, and add them until the sum is around the 50% of the problem space (problem space=the sum of all your values).

Why around 50%? Because if you pick a target value over 50% of the problem space, let's say 80%, by using DP, you can just build up the sums for the subsets and check for the 'negative' subset, as probably you can do with BT, so any target value deviating from the middle location is not that harder (because is near the beginning or the end, in the middle is equidistant, thus is the hardest of the locations for the target value)

However, in my opinion, the concept of 'hard instance' for a subset sum solver depends a lot on the solver implementation details, each solver can face problems with different parameters, e.g: DP can't handle a big $P$ because it blows up the memory need to hold the dynamic table in memory, even with very smart optimizations, the DP 'cost' depends on the target value, and in its worst case the target value for DP is a value around $2^{P-1}*N$, so any change on $P$ or $N$ will impact the 'cost'.

If we look to the meet-in-the-middle, $P$ is not that important (if we don't consider memory), and $N$ is the real problem, when you get to larger sets, even with the smart split the 'cost' will increase exponentially.

So the bottom line is to know what variables impact your algorithm performance to be able to create proper hard instances for 'test benching'

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.