15
$\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 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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I wasn't getting any answers so I've cross posted to mathoverflow: mathoverflow.net/questions/38063/… $\endgroup$
    – user834
    Commented Sep 8, 2010 at 16:33
  • $\begingroup$ This is a very interesting question, I'm also waiting for answers. You are basically asking for a polynomial-time reduction (maybe random) from Subset sum or NPP to integer relation. How about this, if $t=0$ is the target of your subset sum problem, and $S$ is a set of positive integers, with $S'$ a solution satisfying $0=\sum_{a\in S'} a$. This is exactly a linear combination with real coefficients equal to 1. If for each $a_i \in S$ you have that $\sum_i a_i < 2^n-1$ there is always a solution, and the mapping to integer relation will also give you a solution. $\endgroup$
    – Marcos Villagra
    Commented Sep 8, 2010 at 23:07
  • $\begingroup$ @Marcos Villagra: your comment is a little hard to parse...one can embed the problem as a subset sum/number partition problem into a lattice (see here for a review), the question is finding a way to restrict coefficients to the desired set (0,1 or -1,1, say). LLL will find an integer relation, even a small one, but just one 2 or 3 as a coefficient will invalidate it as a subset sum/number partition answer. $\endgroup$
    – user834
    Commented Sep 13, 2010 at 12:35

1 Answer 1

Reset to default
2
$\begingroup$

Let m be the logarithm of the largest number. If $m=O(\log n)$ then it is solvable in polynomial time using dynamic programming. In general, every known algorithm take at least $\Omega(2^{m})$ time. There is no known polynomial time algorithm when $m=\omega(\log n)$ and $m=o(n)$

However, Flaxman and Przydatek provide an algorithm that solves Medium-Density Subset Sum Problems in Expected Polynomial Time.

Check this reference:

Flaxman and Przydatek, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This result is only for choosing the numbers in the Subset Sum instance significantly lower than I want. They choose the range of numbers on the order of log(n)^2 whereas I am interesting in the range of numbers on the order of 2^n. There are well known algorithms to solve Subset Sum when the range of numbers is restricted to be so low and it looks like they've just extended this range a bit, which is great, it's just not what I was looking for. Thank you though. $\endgroup$
    – user834
    Commented Sep 8, 2010 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.