Cheap and Secure Web Hosting Provider : See Now

[Solved]: Find vectors with elements of finite fields that sum up to given value

, , No Comments
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 $\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?

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

0 comments:

Post a Comment

Let us know your responses and feedback