On the computational complexity of the solution of linear systems with moduli (Q1916984)

The paper deals with the computational complexity of the solution of equations of the form \(Ax= D|x|+ \delta\). Note that the problem of computing vertices of the convex hull of the united solution set for a regular system of linear interval equations reduces to the above-mentioned system. The main problem is to find a polynomial-time algorithm that finds out whether the linear system with moduli is solvable for given matrices \(A\), \(D\) and vector \(\delta\), and, in case of solvability, computes a solution to the system. The first theorem proves that the problem of solvability of the linear system with moduli is NP-complete, if \(A\) is nonsingular, \(A\geq D\geq 0\), \(\delta\geq 0\) (the inequality ``\(\geq\)'' is understood componentwise), and the number of solutions of the system is finite (possibly zero). For an arbitrary system of \(m\) equations of \(n\) variables, Theorem 2 proves that there exists a polynomial-time algorithm of order \(O((\max\{m, n\})^3)\) that finds out whether the system is solvable and computes a solution (in case of solvability) if \(A\) and \(D\) are rational matrices, \(b\) is a rational vector and \(D\geq 0\), \(\text{rank}(D)= 1\). In a more general context, Theorem 3 states that, if \(A\), \(D\) are rational \(m\times n\)-matrices, \(b\) is a rational \(m\)-vector, and \(\text{rank}(D)+ \text{corank}(A)\leq k\), there is a polynomial-time algorithm of order \(O((\max\{m, n\})^{k+ 5})\) that finds out whether the linear system with moduli is solvable, and computes a solution in case of solvability.