**Problem Detail:**

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:

- $\{1,0\}$
- $\{1,0,-1\}$
- $\mathbb{N}$
- $\mathbb{Z}$

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.?)

###### Asked By : user3613886

#### Answered By : D.W.

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39992

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback