MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 as well, but have not been getting any answers, so I've cross posted here.

share|cite|improve this question
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:… – Robin Kothari Sep 8 '10 at 15:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.