Find vectors with elements of finite fields that sum up to given value

Question

Given a universe $U$ consisting of k sets of vectors with each vector $\vec{v} \in {\mathbb{F}_{p^m}}^n $. Given also another vector $\vec{c} \in {\mathbb{F}_{p^m}}^n$. Now decide if there is a set $X$ with $|X| = |U|$ and $X_i \in U_i, i = 1,2,...,k$ such that $\sum\limits_i X_i = \vec{c}$. If there is, output this set.

In other words, I want to find a combination of one element out of each set that sums up to the given vector, given that the vectors' entries can only be the results of modulo operation with a given integer. I hope the problem becomes clear.

I want to find an efficient algorithm to solve this problem. It seems to me that it is NP-complete, but I find no other NP-complete problem that I can reduce. If there is one, existing algorithm (if any) to that other problem could be used for this problem.
I looked at integer programming, but I did not find anything with respect to finite fields.

Any ideas?

Answer 1

It looks like subset-sum problem. It should be possible to adapt the pseudopolynomial algorithm.

• Hebi: Thanks adriaN. Yes, I already had a look at the pseudo-ploytime algorithm. The problem there is, that an nxm array is needed where n is number of vectors, m is number of possible sums of vectors, which will be quite much with e.g. vector length 100 and values 1-5. So I would rather only save positive entries. Doing that, for n << m the algorithm would behave like exptime, or am I mistaken?
• adrianN: You might get some good speedup in practice by solving the problem componentwise and cutting off computation when one component doesn't fit.
• Hebi: Yes, I can do that componentwise. Then I have to store the possible results for each component and check if there is a common result for all. Thats all possible in pseudo-polytime, I think. I'll try that. Thank you!
• Hebi: Ok, I tried that. But the possible solution of each component is an exponentially large tree (storage is only finite field length x number of vectors, but traversal behaves exponential). So to find a common solution I would need to traverse those trees. But I realized that my problem is equal to subset sum with large numbers, where no efficient algorithms are known. So I'll probably won't get a better answer...

Answer 2

If $p=2$ and $k\ge mn,ドル you can solve this efficiently (in polynomial time) using linear algebra.

Here's the algorithm. Keep only two elements in each set $U_i,ドル and throw all the rest away, so that $|U_i|=2$ for all $i$. Now if $U_i=\{a_0,a_1\},ドル we can write $a_b = a_1 + b (a_0-a_1)$ (where $b\in \{0,1\}$), and the latter expression is linear in $b$. So, we can write $\sum_i X_i$ as $\sum_i a_{i,1} + b_i (a_{i,0} - a_{i,1}),ドル which is a linear expression in the $k$-vector $b=(b_1,\dots,b_k)$. Let $M$ be the $mn \times k$ matrix over $\mathbb{F}_{2}$ such that $\sum_i X_i = M b$ (expressing each element of $\mathbb{F}_{2^m}$ as a $m$-vector over $\mathbb{F}_2$ using some standard basis).

Now our goal is to find a solution to $M b = c,ドル where $M,c$ are given and our goal is to find $b$. Since this represents $mn$ equations in $k$ unknowns and $k\ge mn,ドル with high probability $M$ is invertible and some solution exists, so Gaussian elimination suffices to find a solution. The solution to $Mb=c$ immediately yields a solution to your original problem. (If $M$ is not invertible and $Mb=c$ has no solution, go back to the beginning and pick a different random two elements of each $U_i$ to keep, and try again. We'll only need to try a constant number of times, on average.)

• Hebi: Nice idea. But if I guess the right combination of pairs of my vectors, then I would still need exponential time, because I would still have to try out each combination of the pairs in each of the k sets, if I understand that correctly.