Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $x$ are non-negative integers.
What is the complexity of this problem? Is there a known algorithm that finds such a solution, or returns false if none exist?
This is NP-hard, by reduction from ILP feasibility. Deciding feasibility of an ILP instance is NP-hard, so your problem is, too.
You can convert each inequality $a_1 x_1 + \dots + a_n x_n \ge b$ into an equality using a slack variable $s \ge 0$:
$$a_1 x_1 + \dots + a_n x_n - s = b.$$
You can arrange for all variables to be non-negative by defining $x_i = x_i^+ - x_i^-$ where the variables $x_i^+,x_i^-$ are non-negative and replacing each $x_i$ with $x_i^+ - x_i^-$.
This transformation turns a system of $m$ linear inequalities in $n$ integer variables into a system of $m+n$ linear inequalities in $2n+m$ non-negative integer variables. Thus the result has exactly the form of your problem.
