I am working out an interesting problem and would like some help with this particular sub problem:

Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\in \left\lbrace 0, 1, -1 \right\rbrace $. For $\vec{x}\in\left\lbrace 1, -1\right\rbrace^m$ we we are presented with the following inequality: $$ M\vec{x} \geq \vec{0} $$ Where $\vec{0}$ is the zero vector in $\mathbb{R}^n$. If you do this out, you will get a system of linear inequalities as follows: $$ a_{11}x_0+\cdots+a_{1m}x_{m-1} \geq 0\\\ \vdots \\\ a_{n1}x_0+\cdots+a_{nm}x_{m-1} \geq 0 $$

Question: What is the time complexity of only deciding whether this system of linear inequalities is feasible, meaning there exists some $\vec{x}\in\left\lbrace 1, -1\right\rbrace^m$ that satisfies the constraints.

Follow up: Can this time complexity be given only in terms of $m$? Perhaps there is some number $C(m)$ (constant with respect to a fixed $m$) for which if $C(m)\leq n$ the time it takes to decide whether a feasible solution exists does not increase futher.

  • $\begingroup$ This is NP-complete, I edited the answer. $\endgroup$ – joro Nov 26 '15 at 13:46

This is NP-complete:

Since $\vec{x}\in\left\lbrace 1, -1\right\rbrace^m$, you are working over discrete domain.

Your entries are over the discrete domain $\{0,1,-1\}$.

Your inequalities can derive equality easily:

$ +x + y + z \ge 0, -x-y-z \ge 0 \iff x+y+z=0$.

The plus sign is $+1$ in the matrix and minus sign is $-1$ in the matrix.

So solving your problem will give solution of linear system with unit coefficients with solutions in $\{1,-1\}$.

NP-completeness follows from positive 1-in-3 SAT.

Given $m$ clauses $[x_i,y_j,z_k]$, it asks for a solution where in each clause exactly one boolean variable is true.

Map True to $1$ and False to $-1$.

Each clause corresponds to the constraint $x_i+y_j+z_k+1=0$ (express equality as described above).

Express $1$ as variable $T \ge 0$.


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.