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?
If[!IntegerQ[...]]
since that is when you have a "witness" to existence of one or more solutions. Also, strictly speaking, that algorithm calls for more space efficient arithmetic than is being done above. $\endgroup$