Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
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

2 Answers 2

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.

share|improve this answer

I'm neither an expert nor too sure, but couldn't this be transformed to a boolean satisfiability problem ? If so, it would be NP-complete.

share|improve this answer
    
You've got to reduce in the other direction to make this conclusion. That is, you would want instead to reduce the satisfiabiliy problem to this one. –  Joel David Hamkins May 28 '10 at 12:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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