The subset sum problem is finding a solution $x \in \{0,1\}^n$ such that
$$\sum_{i=1}^n a_i x_i = c,$$
for $a_i, c \in \mathbb{F_q}$ (also possible for $a_i,c \in \mathbb Z$).
I know that there exists a pseudo polynomial solution to this via dynamic programming. Sadly I am not very skilled at dynamic programming yet so I was wondering if a pseudo polynomial solution was possible to the following variation on a multiple subset sum problem.
Instead of $1$ equation we are working with $2$ or more, so we need to find a solution $x \in \{0,1\}^n$ such that
$$\sum_{i=1}^n a_i x_i = c_1,$$
$$\sum_{i=1}^n b_i x_i = c_2,$$
for $a_i,b_i, c_1, c_2 \in \mathbb{F_q}$.
To give you some intuition, when we would have $n$ such equations this would be solvable via Gaussian elimination.
In this case all the coefficients are positive and bounded.
I was wondering if this would be solvable via dynamic programming such that we would have a pseudo polynomial algorithm or if this isn't possible an explanation why.
I hope you guys can help me!
Best Answer
It is possible to modify the "classical" dynamic programming algorithm for one set of numbers to remember the solutions it computes (although this might result in a combinatorial explosion...).
Afterwards, you may run it for the first equation (check if there is a subset of $a_1, \ldots, a_n$ that sums up to $c_1$), and then check if any of the found solutions work for $b_1, \ldots, b_n$ and $c_2$.