2
$\begingroup$

Are there any bounds for the subset problem with respect to the number of the terms involved in the sum and the range of the possible values?For example looking for some 2 terms whose sum equals 3 you know that those two numbers are either $(1,2), (2,1)$ if both $a,b \in \mathbb{N}$. So it is pretty easy to find. How can we bound the difficulty of a polynomial time solver of this problem with respect to the number of the terms and the possible combinations in between them knowing a priori the sum?

$\endgroup$
5
$\begingroup$

Here is some information on random instances of subset sum. This should give you a starting point at least.

The main factor influencing the computational difficulty of solving (random instances of) subset sum is the relationship between the number of available terms, $n$, and the terms' size, $M$. (This is different than the 'possible combinations' idea you were expressing before... Nonetheless:)

For simplicity in relating the two (and incidentally, to get an algebraically symmetric problem), we can write subset sum formally as..


Given $a_1, ..., a_n, T\in\mathbb{Z}_M$,

where the $a_i$ are chosen uniformly and $T$ is a sum of a random subset of the $a_i$, find a subset of the $a_i$ that sum to $T\pmod M$.

That is, given the $\{a_i\}$ and $T = \sum_{i\in S} a_i\pmod M$, for some (unknown, random) $S\subseteq [n]$,

find $S'\subseteq [n]$ such that $T = \sum_{i\in S'} a_i\pmod M$. ($S = S'$ is one possible solution.)


The following is known:

  • When $M = 2^{\Omega(n^2)}$, random subset sum can be solved in polynomial time using lattice reduction techniques. See Lagarias/Odlyzko, "Solving low density subset sum problems," JACM 1985.
  • Similar techniques to the above yield subexponential time algorithms when $M > 2^{n^{1+\epsilon}}$.
  • When $M = 2^{O(\log^2 n)}$, random subset sum can be solved in polynomial time using a 'generalized birthday attack'-type algorithm. See Flaxman/Przydatek, "Solving medium-density subset sum problems in expected polynomial time," STACS 2005.
  • When $M < 2^{n^{\epsilon}}$ for $\epsilon < 1$, there is a $M^{O(\frac{1}{\log n})}$-time algorithm due to Lyubashevsky; see "The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem," RANDOM 2005.

In other words, the hardest instances of subset sum seem to be when $M = 2^{\epsilon n}$ for $\epsilon < 1$, for which we only know a $2^{\Omega(n)}$-time algorithm.

$\endgroup$
  • $\begingroup$ At your last sentence you wanted to say $M = 2^{\epsilon n}$ or $M = 2^{n^{\epsilon}}$ ? $\endgroup$ – curious Jan 29 '14 at 9:54
  • $\begingroup$ curious-- it's written correctly, $2^{\epsilon n}$ are the hard instances. $2^{{n}^\epsilon}$ has the faster (subexp) algorithm. $\endgroup$ – Daniel Apon Jan 29 '14 at 13:39

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.

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