How to generate hard subset sum instances

Question

A subset sum problem can be defined as:

• Given a set of integers $S$
• A target integer $x$
• Find some subset of elements $s \in S$ such that $\sum_0^{n}s_i = x$

The "density" of a subset sum problem is defined as: $\text{density} = \frac{k}{\operatorname{log}(\operatorname{max}(S))}$

Where $k$ is the number of elements in the set $S$ and $\operatorname{log}(\operatorname{max}(S))$ is the size of the largest element in the set.

Subset sum problems of density $\lt 0.9408$ can be solved in polynomial time.

I would like to know:

• How can we generate hard instances of the subset sum problem that are not solvable in polynomial time, or more specifically, require exponential time to solve?
  • Is it sufficient to use any size set and with elements such that $\text{density} = 1$? Assume that all set elements are uniformly random and of size $\operatorname{log}(\operatorname{max}(S))$
  • Is a higher density necessarily more difficult?
• Supposing we can generate problems that require exponential time to solve, what parameter is the problem exponential in?
  • A set of size $8$ with $8$-bit elements has a density of $1$, and so does a set of size $256$ with $256$-bit elements, so if $\text{density} = 1$ is the requirement for hardness then it wouldn't make sense for the running time to be exponential in the density parameter.

Answer 1

How can we generate hard instances of the subset sum problem that are not solvable in polynomial time, or more specifically, require exponential time to solve?

Is it sufficient to use any size set and with elements such that $\text{density}=1$? Assume that all set elements are uniformly random and of size $\operatorname{log}(\operatorname{max}(S))$

Supposing we can generate problems that require exponential time to solve, what parameter is the problem exponential in?

Conditions and Parameters

The hardest instances have $\text{density} = 1$.

An instance of the problem with $\text{density} = 1$ will require time exponential in the number of elements that are summed together.

To generate hard instances of the problem, ensure that:

• The number of elements in the set $k$ is equal to the the size of the largest element in the set (in bits)
• All elements in the set are approximately that size (you can't have a single element of size $\operatorname{log}(k)$ and the rest of the elements small).
• Each instance should sum ($k / 2)$ of the elements of the set together.
  • If you were to sum $k - 1$ elements of the set together, then you could solve an easier problem (namely: subtract elements from the sum of the entire set until you find which one(s) isn't a member of the target subset)

Cost

Basically, you need $k$ uniformly random elements of size $\operatorname{log}(k)$ for a hard instance of the problem. This implies that a hard instance of the problem will require $O(k^2)$ space.

There is a quantum attack against the subset sum problem that runs in time $O((0.241... + O(1)) * n)$, which we will round to $O(.25 * n)$ to make the following math more convenient:

Assuming the complexity of the quantum attack cited above using the conditions laid out above, the computational cost to solve a subset sum problem of size $k$ is $O(2^{k / 8})$.

• To generate instances of the problem that require approximately $O(2^{128})$ computational cost against a quantum adversary, set $k = 1024$.
  • This will use $1024^2 = 1048576$ bits of space.

Is a higher density necessarily more difficult?

No, instances of the problem with $\text{density} > 1$ are more easily solved.