-3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It came up studying another problem on simplicial complexes. In this case $A$ is the boundary matrix and I am looking for a chain with non-negative coefficients whose boundary is $b$. It didn't seem straightforward to me, could you elaborate on why you think it is? $\endgroup$ – Will Apr 2 at 3:45
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.