On the computational complexity of the solution of linear systems with moduli

摘要

A problem of solvability for the system of equations of the formAx=Dx+δis investigated. This problem is proved to beNP-complete even in the case when the number of equations is equal to the number of variables, the matrixAis nonsingular,A≥D≥0,δ≥0, and it is initially known that the system has a finite (possibly zero) number of solutions. For an arbitrary system ofmequations ofnvariables, under additional conditions that the matrixDis nonnegative and its rank is one, a polynomial-time algorithm (of the orderO((max{m, n})3)) has been found which allows to determine whether the system is solvable or not and to find one of such solutions in the case of solv