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.