Time Complexity of Exhaustive Search Algorithm

I have the sets $S_1=\{2,10,20,6\}$ and $S_2=\{25,26,20\}$ and I want to find which numbers sum to make 32. This is very easy by inspection; 6 and 26. It seems similar to the Knapsack problem, but I am no expert.

However, say I have 1000 sets, each with 500 elements such that summing one term from each set always gives you a unique value. This is much harder to inspect and solve, especially if the sets follow a structure that will appear random (they would be constructed from structured sets that have been messed with, and it would be near impossible to guess the mixing and reverse the sets).

So, the only way must be an Exhaustive Search Algorithm. Given my number is 52,485,332, there are $1000^{500}$ possible options to look at. Indeed there will be ways to shorten this search (such as when a set has numbers larger than your target value, you can ignore those numbers). But otherwise you might still be looking at $750^{500}$ possible choices.

So, what is the time complexity of such a search algorithm? $O(n^{k})$, with $n$ the number of sets and $k$ the number of elements in those sets? They have to check "all" possible combinations of terms until one matches the given value.

The main questions seem to be "how many sets are there?" and "how large are the sets?". Indeed, the sets can also all be of various sizes, not just uniform.

I am not a cryptography person; my research just flirts with the idea at hand. Any help would be appreciated.

So, the only way must be an Exhaustive Search Algorithm

As I mentioned in my comment, there are practical methods for nonhuge values of $m$ (and $m=52485332$ is not huge). Here is the outline of one such method (which assumes all the sets consist of nonnegative integers):

• We have an array $A_{n, m+1}$; each element of the array $A_{a, b}$ will note how we can generate the sum $b$ from the first $a$ sets (or $\perp$ if no such way has been found yet).

• Initialize all elements $A$ to $\perp$

• For $i := 1$ to $n$ search the elements $A_{i-1}$ for non-$\perp$ element (and for $i=1$, the 0th element is treated as the only non-$\perp$ element. For each such element $A_{i-1, x}$, set $A_{i, x + S_{i,j}}$ to $j$ (for each element $S_{i,j}$ of the set $S_i$) If $x + S_{i,j} > m$, ignore it.

• Finally, if $A_{n,m} = \perp$, there is no subset that leads to the sum $m$. If it is anything else, we can recover the terms by backtracking through the array $A$.

This should be a practical algorithm for recovering the terms given the parameters you have specified.

This is more an answer to why the uniqueness of the sums effects the size so much that the case for $52485332$ becomes trivial (its way to long for a comment).

When all sums must be unique, then they must result in different integers. Because there are $500^{1000}$ possible sums, there are also $500^{1000}$ different integer results for that. the lowest case would be all integers from $0$ to $500^{1000}-1$.

For Example,

$S_1 = \{0, 1, 2, ..., 499\}$

$S_2 = \{0, 500, 1000, ..., 249500\}$

$S_3 = \{0, 250000, 500000, ..., 124750000\}$

...

$S_{1000} = \{0, 500^{999}, 2*500^{999}, ..., 499*500^{999}\}$

would be a way to ensure the uniqueness of the result. As you can see, The Numbers get really large really fast.

In this particular example its easy to find the result (just always choose the largest number that fits from last to first set). Even most numbers is $S_3$ are greater than $52485332$ and can therefore be ignored.

You would probably want relatively random values in your sets. In this case the range of the values have to be at least slightly larger.

However, it is highly unlikely that any value is lower or equal to $52485332$ (when you uniformly choose $500000$ values out of $500^{1000}$)

Dynamic programming, as @poncho suggested, really only works for small numbers and its performance is not that much better than exhaustive search (linear difference in the number of sets), because the sub-sums, that can be reused are unique, the advantage of not looking at other possibilities is not there. Runtime should be same order as exhaustive search. Only improvement is to aboard when values are to large or small to reach the target, but for reasonable targets that is not much of an advantage.

On could easily reduce the subset sum problem or knapsack problem to this one by just using the same set as many times as the number you want to sum to. Problem with this is that this is not a polynomial time reduction ant therefore not sufficient to proof if problem is NP hard.