Why does SUBSET-SUM, sometimes, trivialize so fast? Say S = {a, b, ... } is a set of integers adding up to d, then I can represent each integer, say a, it with its bitwise encoding an, .., a0, and you end up with (a bit confusing but c is the carry, an expression in terms of variables of the following column):

    cn  cn-1 ... c1 c0 
    an  an-1 ... a1 a0 . s0
    bn  bn-1 ... b1 b0 . s1
    dn  dn-1 ... d1 d0

Now, a,b,.. and d are constants so if you would fill in the zeroes and ones, you'ld end up with something like:

    cn  cn-1 ... c1  
    s0   0   ... s0  0
    s1  s1   ...  0 s1
     0   1   ...  1  0

Now you can manipulate si out by replacing them with the xor of the rest of the column, the digit and the carry - especially when taking into account the carry expression and the fact that you can swap rows. Guess I should read somewhat. [Abraham D. Flaxman and Bartosz Przydatek, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time.] Right, there's a whole folkflore around this problem, the article was on mod M problems with medium density, its a probabilistic algorithm with an expected running time.

Tinkering... Its not too exciting...