NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations

Abstract

Three series of number-theoretic problems with explicitly defined parameters concerning systems of Diophantine dis-equations with solutions from a given domain are considered. Constraints on these parameters under which any problem of each series is NP-complete are proved. It is proved that for any m and m′ (m < m′) the consistency problem on the segment [m, m′] for a system of linear Diophantine dis-equations, each of which contains exactly three variables (even if the coefficients at these variables belong to {–1, 1}), is NP-complete. This problem admits a simple geometric interpretation of NP-completeness for the determination of whether there exists an integer-valued point inside a multidimensional cube that is not covered by given hyperplanes that cut off equal segments on three arbitrary axes and are parallel to all other axes. If in a system of linear Diophantine dis-equations each dis-equation contains exactly two variables, the problem remains NP-complete under the condition that the following inequality holds: m′–m > 2. It is also proved that if the solution to a system of linear Diophantine dis-equations, each containing exactly three variables, is sought in the domain given by a system of polynomial inequalities that contain an n-dimensional cube and are contained in an n-dimensional parallelepiped symmetric with respect to the point of origin, its consistency problem is NP-complete.