2
$\begingroup$

May be it's a stupid question (sorry if it's the case).

What is the complexity the decision problem:

Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$

does there exists $x\in\mathbb{N}^n,x>0$ such that $Ax\geq 0$?

Where $x\geq 0$ means for all $x_i\geq 0$ and $x>0$ means there exists $x_j>0$.

I know that integer linear programming is NP-complete but it's expressed has $Ax\leq b$ and I failed to reduce $Ax\leq b$ to $Ax\geq0$ ...

$\endgroup$
4
$\begingroup$

Your problem is in polynomial time, as the following claim implies.

Claim Let $A$ be an $m\times n$ matrix with rational entries. There exists an integer $x > 0$ such that $Ax \geq 0$ if and only if there exists a real $x > 0$ such that $Ax \geq 0$.

Proof The forward implication is trivial. For the backward implication, suppose that there exists a real $x > 0$ such that $Ax \geq 0$. In particular, the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty. Pick some vertex $x$ of $P$. Since all entries of $A$ are rational, all coordinates of $x$ are also rational. Therefore for some integer $N>0$, all entries of $Nx$ are integral. Furthermore $Nx > 0$ and $A(Nx) = N(Ax) \geq 0$. $\square$

Given a matrix $A$, in order to determine whether there exists a real $x > 0$ such that $Ax \geq 0$, check whether the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty using linear programming. This can be done in polynomial time.

$\endgroup$
  • $\begingroup$ Wait ... Why it doesn't work for the decision version of integer linear programming which is NP? $\endgroup$ – wece May 23 '13 at 18:52
  • 1
    $\begingroup$ @wece because when you scale a rational $x$ by $N$ so that $Nx$ is integral, the constraint $A(Nx) = N (Ax) \leq b$, does not have to hold for arbitrary $b$. $\endgroup$ – Sasho Nikolov May 23 '13 at 20:31
  • $\begingroup$ @SashoNikolov :S thanks I feel stupid now. $\endgroup$ – wece May 23 '13 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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