Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
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? –  Hebi Nov 28 '12 at 18:04
    
You might get some good speedup in practice by solving the problem componentwise and cutting off computation when one component doesn't fit. –  adrianN Nov 29 '12 at 9:38
    
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 Nov 30 '12 at 11:27
    
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... –  Hebi Dec 8 '12 at 16:48
add comment

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

share|improve this answer
    
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. –  Hebi Oct 20 '13 at 20:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.