Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic sense?
I know that LLL (and perhaps PSLQ) have been used with moderate success in solving Subset Sum problems in the 'low-density' region, where the range of numbers chosen is less than $2^N$, but these methods don't scale well to instances of larger size and fail in the 'high-density' region, when the range of numbers chosen is much larger than $2^N$ (to be clear, LLL finds small integer relation solutions, just not 0-1 solutions required to be a solution to the Subset Sum instance).
Integer relation detection is polynomial to within an exponential bound of optimal whereas Subset Sum and NPP are obviously NP-Complete, so in general this is probably not possible, but if the instance is drawn uniformly at random, could this make it simpler?
Or should I not even be asking this question and instead be asking if there is a way to reduce the exponential bound from the optimal answer in lieu of an exponential increase in computation? Is there even a way to 'interpolate' the LLL algorithm so that as you tune a parameter the bound becomes tight at the cost of an exponential increase in computation?
note: I've asked this over at cstheory.stackexchange.com as well, but have not been getting any answers, so I've cross posted here.
