Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The integer feasibility problem is NP-complete:
$Ax=b, x \geq 0, x \mbox{ integer}$
$A$ contains elements in $\mathbb{R}$
If we restrict this:
$A$ contains only elements in:
Does this change anything in term of hardness?
Can all these problems be reduced to each other?
(Can it be for example that there is polynominaltime-algorithm for 1. but not for 4.?)
All four problems are NP-complete.
Let me start by proving two easy results:
Your problem #3 is NP-complete, even when the matrix has only a single row, as explained here: Complexity of a subset sum variant.
This implies that #4 is NP-complete as well, as #3 is a special case of #4.
Now for the strong result: Your problem #1 is NP-complete. The proof of this is a bit more involved, but I'll show a reduction from ZOE to your #1, where ZOE is a problem that is known to be NP-complete.
In particular, here is the definition of ZOE:
ZERO-ONE EQUATIONS (ZOE)
Input: a $m\times n$ matrix $A$, all of whose entries are 0 or 1
Goal: Find a $n$-vector $x$, all of whose entries are 0 or 1, such that $Ax=1$, where $1$ denotes the all-ones vector
The ZOE problem is NP-complete. This is proven in Chapter 8.3 of Algorithms (Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani). The proof proceeds by reducing 3SAT to 3D Matching, and then reducing 3D Matching to ZOE.
Now we can reduce ZOE to #1, as follows. If we have an instance of ZOE $A$, we transform it as follows. For each variable $x_i$ of the ZOE instance, we add another variable $x^*_i$ and an equation $x_i + x^*_i = 1$. (This has the effect of forcing $x_i$ to be either 0 or 1, since we'll require $x_i \ge 0$ and $x^*_i \ge 0$ and $x_i,x^*_i$ are integers.) Thus, if the ZOE instance had a $m\times n$ matrix $A$, we now obtain $m+n$ equations in $2n$ unknowns, corresponding to some matrix $A'$. In other words, we obtain a problem instance $A'x' = b$ where $b=1$ is the all-ones vector, and where every entry of $A'$ is 0 or 1. This is now an instance of your problem #1. This instance of your problem #1 has a feasible solution if and only if the original ZOE instance has a feasible solution. This proves that any efficient algorithm to your #1 in turn yields an efficient algorithm for ZOE -- but since ZOE is NP-complete, it follows that #1 is NP-complete as well.
It follows from this result that #2, #3, and #4 are NP-complete as well, as #1 is a special case of them.
Partial answer: (3) and (4) can be reduced to (2), at the price of increasing the problem size by a factor in $O(\log N)$, where $N$ is the greatest matrix entry in the original problem. One way of doing this (possibly suboptimal) is to have for each original variable $x$ pairs of new variables $x_i,\bar x_i$ ($0\le i\le \log N$) representing $2^ix$, which is enforced by the additional constraints $x_i-\bar x_i=0$ and $x_{i+1}-x_i-\bar x_i=0$. Now replace each term $mx$ in the linear constraints by the appropriate combination of $x_i$, and you are done.
