Trichotomy for integer linear systems based on their sign patterns

In this paper, we consider solving the integer linear systems, i.e., given a matrix A∈Rm×nA∈Rm×n, a vector b∈Rmb∈Rm, and a positive integer dd, to compute an integer vector x∈Dnx∈Dn such that Ax≥bAx≥b or to determine the infeasibility of the system, where mm and nn denote positive integers, RR denotes the set of reals, and D={0,1,…,d−1}D={0,1,…,d−1}. The problem is one of the most fundamental NP-hard problems in computer science.For the problem, we propose a complexity index ηη which depends only on the sign pattern of AA. For a real γγ, let ILS(γ) denote the family of the problem instances II with η(I)=γη(I)=γ. We then show the following trichotomy: •ILS(γ) is solvable in linear time, if γ<1γ<1,•ILS(γ) is weakly NP-hard and pseudo-polynomially solvable, if γ=1γ=1,•ILS(γ) is strongly NP-hard, if γ>1γ>1. This, for example, includes the previous results that Horn systems and two-variable-per-inequality (TVPI) systems can be solved in pseudo-polynomial time.