2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ When cross-posting, it's usually a good idea to include a link to the other question, so that we don't end up having two independent discussions on the topic. In this case the other question has no answers, so we're safe, but here's the link anyway: cstheory.stackexchange.com/questions/1066/… $\endgroup$ – Robin Kothari Sep 8 '10 at 15:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.