Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables

Question

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.

Answer 1

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$.