# NP Complete for range sum constraints?

Is the following problem NP Complete?

We have $n$ variables $x_1$,$x_2$,....,$x_n$ and a set of constraints:

$\sum_{i=a_1}^{b_1}x_i = h_1$

$\sum_{i=a_2}^{b_2}x_i = h_2$

$\sum_{i=a_3}^{b_3}x_i = h_3$

......

where $h_1$,$h_2$,...,$h_n$ are integers. We ask for an integer assignment of $x_1$,$x_2$,...,$x_n$.

The constraint matrix does not seem to be totally unimodular. Is the problem NP Complete?

-
I took the liberty of reformatting your question. It is a good idea to write your question with care if you want useful answers. Does NPC stand for NP Complete? – François G. Dorais May 26 '10 at 0:52
Thanks Francois. Yes, NPC stands for NP Complete. -Jian. – Jian May 26 '10 at 15:39
I think I got a proof that the constraint matrix is totally unimodular. but still be great if any one can provide a ref. – Jian May 26 '10 at 16:19
Could you clarify whether the number of constraints is fixed at three, or are we considering the general problem with an arbitrary number of constraints? And it is truly important for you that the constraints range over an interval of the indices? For example, if we are allowed to form constrainsts from any subset of the indices, then it would seem easier to prove NP Completeness. Finally, could you edit the question and title to expand the abbreviation NPC? Click on 'edit'. – Joel David Hamkins May 28 '10 at 13:02
THere could be arbitrary number of constraints. Each one is a range sum constraint. The constraint matrix is totally unimodular, thus the problem is in P. Thanks anyway. – Jian Jun 4 '10 at 21:51

The problem is equivalent to checking whether the vector $(h_1,\dots,h_m)$ belong to the integer lattice $$\{ Ax \mid x\in \mathbb{Z}^n \}$$ where $A$ is a given $m\times n$ integer matrix. This problem is known to belong to $P$.
However, there exists a similar problem that is indeed $NP$-complete - namely, checking whether a given vector belongs to the integer cone $$\{ Ax \mid x\in \mathbb{Z}_+^n \}.$$
The crucial difference is that in the first problem variables $x_1,\dots,x_n$ can be arbitrary integers, while in the second problem they have to be nonnegative integers. And this nonnegativity requirement turns a polynomial-time problem into an $NP$-complete one.