Implementing Kane's Subset Sum Algorithm

Question

In the following paper, D. Kane describes an algorithm for subset sum that runs in logspace: http://arxiv.org/pdf/1012.1336v2.pdf.

I am trying to implement it

subsetsum[sum0_, set0_] := Module[{sum = sum0, set = set0},
c = 0;
csum = Abs[sum] + Total[set] + 1;
p = NextPrime[csum];
n = Length[set];
check = False;
While[c <= n,
Print["c=" <> ToString[c] <> "p=" <> ToString[p]];
If[IntegerQ[Sum[x^(-sum)*Product[(1 + x^(set[[i]])), {i, 1, n}], {x, 1, p - 1}]/p],
check = True; Break[];];
c = c + Floor[Log[2, p]]; p = NextPrime[p];
];
check
];

This initial value $C$ which seems to be the $C$th prime or the next prime after $C$ is given as:

$ C = \lvert B \rvert + \sum_{i=1}^n \lvert m_i \rvert +1 $

$B$ is the sum to which a subset of some set $\{m_1,m_2,m_3,\ldots,m_n\}$ sum to.

Furthermore, on a simple instance such as:

    set = {2, 3, 5, 7, 8, 9};
    sum = 9;
    subsetsum[sum, set] 

the program seems to stop after 2 loops returning False... which is wrong. It should be returning true...

Anyone has any ideas on this?

Answer 1

[Okay, I realize this isn't an answer but it's a sort'a neat way to get those coefficients.]

One can alternatively use the Cauchy Integral Formula to get the appropriate coefficient of the product polynomial that enumerates the possible subset sums. Below is a numerical implementation. A symbolic version can of course be coded, but it would in effect be computing the coefficients explicitly.

residue[ll_, n_] := Module[
  {x, logsum, pts, m = 1101, vals},
  logsum = Total[Log[1 + x^ll]] - n*Log[x];
  pts = N[1/2*Exp[2*Pi*I*Range[0, m - 1]/m], 200];
  vals = Exp[logsum /. Transpose[{Thread[x -> pts]}]];
  Total[vals]/m
  ]

Here is an example of usage.

vals = Union[NextPrime[RandomInteger[{1, 100}, 20]]]

(* Out[184]= {7, 11, 17, 29, 37, 41, 43, 53, 59, 67, 79, 89, 101} *)

This next function computes the coefficients explicitly so we can compare.

coeffpoly[ll_] := 
 Rest[Module[{x}, CoefficientList[Times @@ (1 + x^ll), x]]]

coeffpoly[vals][[358]]

(* Out[198]= 38 *)

SO there are 38 ways to form the value 358 as a subset sum of vals. Now we do this using residue.

residue[vals, 358]

(* Out[203]= \ 38.0000000000000000000000000000000000000000000000000000000000000000000\ 0000000000000000000000 + 0.*10^-90 I *)

Almost seems like magic. The weaknesses are

(1) One cannot get away with m=1101 in general. The integral approximation could need arbitrarily many terms.

(2) One cannot rely on numerical precision of 100 in general. This too might have to be ratcheted arbitrarily high.

As subset sums are NP complete clearly one or the other will have to go beyond polynomially large in the size of the input in order to make this into a fully reliable method. I do not know if it is possible to get "usually" acceptable approximations in a way that stays in polynomial complexity. I suspect that, at least for the class of subset sums for which lattice reduction methods usually work, the approach above would not require exponential resources in the problem size.