Problem Detail: 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 $sumlimits_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?
I looked at integer programming, but I did not find anything with respect to finite fields. Any ideas?
Asked By : Hebi
Answered By : adrianN
It looks like subset-sum problem. It should be possible to adapt the pseudopolynomial algorithm.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6968 Ask a Question Download Related Notes/Documents
