CS3343/3341
 Analysis of Algorithms 
   Subset Sum Problem  

Hard Instances of Subset Sum: Because of the existence of dynamic programming algorithms for Subset Sum, no SS instance can be hard unless the positive integers in the instance are very large If the numbers are very large, then the size of the work array W would have to be very large, and so processing W will take excessive time, not to mention the fact that the computer's memory will not hold W. However, as the example below shows, an instance of SS with large numbers may still be tractable (efficiently solvable).

Here is an instance of SS with 20 numbers, where each number is between 1013 and 1014. In order to use dynamic programming in this case, we would need the array W to have size at least 1015. That many long integers would be nearly 1016 bytes, which is about 10,000 terabytes.

13174331003415  17285145771356  19133308147607  20768399988658  22857403444525  
27320889680330  32609413435035  33346249486015  36451703583100  44137263807532 
44383378110073  46011207828303  46660233846241  48665987443489  50851895884076  
54719671502113  57124392416851  84622296739659  91977495188814  97454623373902

The sum of the red integers is: 401687963698840. However, there is an approach in this case: choose a convenient number m, say m = 1000000. Take remainders of all numbers on division by m (one says "handle numbers mod m"), and do all the calculations mod m, so that the sum will also be mod m. Here is the result: 

  3415 771356 147607 988658 444525 
680330 435035 486015 583100 807532 
110073 828303 846241 443489 884076 
502113 416851 739659 188814 373902

Notice that each number is just the low 6 digits of the numbers above. The sum of the red numbers in this case is 5698840, and we have 5698840%1000000 = 698840, the same as the low order 6 digits of the large sum above. In looking for sums of these numbers, we would try 698840, 1698840, 2698840, 3698840, 4698840, 5698840, and find the subset on the 6th try. We also might get spurious results, but it looks as if instances similar to the one here can also be solved efficiently. Notice that this doesn't mean that there are not hard instances of SS, but just that it can be hard to find hard instances.

Revision date: 2012-10-29. (Please use ISO 8601, the International Standard Date and Time Notation.)