2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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? $\endgroup$
    – François G. Dorais
    Commented May 26, 2010 at 0:52
  • $\begingroup$ Thanks Francois. Yes, NPC stands for NP Complete. -Jian. $\endgroup$
    – Jian
    Commented May 26, 2010 at 15:39
  • $\begingroup$ I think I got a proof that the constraint matrix is totally unimodular. but still be great if any one can provide a ref. $\endgroup$
    – Jian
    Commented May 26, 2010 at 16:19
  • $\begingroup$ 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'. $\endgroup$
    – Joel David Hamkins
    Commented May 28, 2010 at 13:02
  • $\begingroup$ 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. $\endgroup$
    – Jian
    Commented Jun 4, 2010 at 21:51

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented May 28, 2010 at 12:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .