Given an oracle that can solve in polynomial time:$$a^Tx=b$$$$x \geq 0$$So it can solve the feasibility problem with one equality-constraint ($a$ is here a vector and $b$ is a constant, $x$ is required to be integer) and non negativity constraint for the solution. (This problem is also known as unbounded knapsack problem)With this oracle how can this be solved in polynomial time:$$Ax=b$$$$x \geq 0$$where there are arbitrary many equality-constraints ($A$ is here a Matrix and $b$ an vector, $x$ is required to be integer) and non negativity constraint for the solution.My thoughts:Just finding a solution for every constraint is not enough. You need to somehow be able to find a solution which fulfills all constraints. But i don't see a way? But there has to be way, because both problems are NP-complete.
Polynomial reduction from unbounded knapsack problem to general integer programming
complexity theory;reductions;integer programming