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 greater 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 smaller than $2^N$. Here low-density and high-density refers to the number of solutions. The low-density region refers to the few or no solutions that exist whereas high density refers to a region with many solutions.
In the high density region, LLL finds (small) integer relations amongst instances given, but as instance size increases, the probability of the relation found being a viable Subset Sum or Number Partition Problem solution becomes decreasingly small.
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?