2026-07-23T13:08:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3436 2024-03-06T10:34:14Z ddc:004 open_access

Trichotomy for Integer Linear Systems Based on Their Sign Patterns Kimura, Kei Makino, Kazuhisa Integer linear system Sign pattern Complexity index TVPI system Horn system In this paper, we consider solving the integer linear systems, i.e., given a matrix A in R^{m*n}, a vector b in R^m, and a positive integer d, to compute an integer vector x in D^n such that Ax <= b, where m and n denote positive integers, R denotes the set of reals, and 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 h which is based only on the sign pattern of A. For a real r, let ILS_=(r) denote the family of the problem instances I with h(I)=r. We then show the following trichotomy: - ILS_=(r) is linearly solvable, if r < 1, - ILS_=(r) is weakly NP-hard and pseudo-polynomially solvable, if r = 1, and - ILS_=(r) is strongly NP-hard, if r > 1. This, for example, includes the existing results that quadratic systems and Horn systems can be solved in pseudo-polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kei Kimura and Kazuhisa Makino 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.613 urn:nbn:de:0030-drops-34367 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.613 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode