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

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

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

<hr>

<p>Given $a_1, ..., a_n, T\in\mathbb{Z}_M$,</p>

<p>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$.</p>

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

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

<hr>

<p>The following is known:</p>

<ul>
<li>When $M = 2^{\Omega(n^2)}$, random subset sum can be solved in <em>polynomial time</em> using lattice reduction techniques. See Lagarias/Odlyzko, "Solving low density subset sum problems," JACM 1985.</li>
<li>Similar techniques to the above yield subexponential time algorithms when $M &gt; 2^{n^{1+\epsilon}}$.</li>
<li>When $M = 2^{O(\log^2 n)}$, random subset sum can be solved in <em>polynomial time</em> using a 'generalized birthday attack'-type algorithm. See Flaxman/Przydatek, "Solving medium-density subset sum problems in expected polynomial time," STACS 2005.</li>
<li>When $M &lt; 2^{n^{\epsilon}}$ for $\epsilon &lt; 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.</li>
</ul>

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

CC BY-SA 3.0
2014-01-29T09:54:58.620Z
At your last sentence you wanted to say $M = 2^{\epsilon n}$ or $M = 2^{n^{\epsilon}}$  ?
curious
CC BY-SA 3.0
2014-01-29T13:39:21.303Z
curious-- it's written correctly, $2^{\epsilon n}$ are the hard instances. $2^{{n}^\epsilon}$ has the faster (subexp) algorithm.
Daniel Apon
CC BY-SA 3.0
2014-01-28T14:29:23.957Z
2014-01-28T14:50:07.267Z
2014-01-28T14:50:07.267Z
Daniel Apon
<p>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?</p>

<cc.complexity-theory><time-complexity><lower-bounds><upper-bounds><subset-sum>
Subset Sum bounds
curious
# Subset Sum bounds

(Asked by: username_0 on 2014-01-28)

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?

**Tags:** cc.complexity-theory, time-complexity, lower-bounds, upper-bounds, subset-sum


---

## 1 answers

### Answer by username_1 on 2014-01-28. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: At your last sentence you wanted to say $M = 2^{\epsilon n}$ or $M = 2^{n^{\epsilon}}$  ?  
> **username_1**: username_0-- it's written correctly, $2^{\epsilon n}$ are the hard instances. $2^{{n}^\epsilon}$ has the faster (subexp) algorithm.  

---

