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.

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.)