TY - JOUR

T1 - NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine congruences and equations

AU - Kosovskii, N. K.

AU - Kosovskaya, T. M.

AU - Kosovskii, N. N.

PY - 2016/4/1

Y1 - 2016/4/1

N2 - Three series of number-theoretic problems with explicitly marked parameters that concerning systems of modulo m congruences and systems of Diophantine equations with solutions from the given segment are proposed. Parameter constraints such that any problem of each series is NP complete when they are met are proved. For any m1 and m2 (m1 < m2 and m1 is not a divisor of m2), the verification problem for the consistency of a system of linear congruences modulo m1 and m2 simultaneously, each containing exactly three variables, is proved to be NP complete. In addition, for any m > 2, the verification problem for the consistency on the subset, containing at least two elements, of the set {0, …, m–1} for the system of linear congruences modulo m, each of which contains exactly three variables, is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-discongruence with the term 2-discongruence in the statement of the theorem. For systems of Diophantine linear equations, each of which contains exactly three variables, the verification problem for their consistency on the given segment of integers is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-equation with the term 2-equation in the statement of the theorem. This problem can also have a simple geometrical interpretation concerning the NP completeness of the verification problem on whether there an integer point of intersection of the given hyperplanes exists that cuts off equivalent segments on three axes and are parallel to other axes inside of a multidimensional cube. The problems of the stated series include practically useful problems. Since the range of values for an integer computer variable can be considered integer values from a segment, if P ≠ NP, theorem 5 proves that any algorithm that solves these systems in the set of numbers of the integer type is nonpolynomial [6].

AB - Three series of number-theoretic problems with explicitly marked parameters that concerning systems of modulo m congruences and systems of Diophantine equations with solutions from the given segment are proposed. Parameter constraints such that any problem of each series is NP complete when they are met are proved. For any m1 and m2 (m1 < m2 and m1 is not a divisor of m2), the verification problem for the consistency of a system of linear congruences modulo m1 and m2 simultaneously, each containing exactly three variables, is proved to be NP complete. In addition, for any m > 2, the verification problem for the consistency on the subset, containing at least two elements, of the set {0, …, m–1} for the system of linear congruences modulo m, each of which contains exactly three variables, is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-discongruence with the term 2-discongruence in the statement of the theorem. For systems of Diophantine linear equations, each of which contains exactly three variables, the verification problem for their consistency on the given segment of integers is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-equation with the term 2-equation in the statement of the theorem. This problem can also have a simple geometrical interpretation concerning the NP completeness of the verification problem on whether there an integer point of intersection of the given hyperplanes exists that cuts off equivalent segments on three axes and are parallel to other axes inside of a multidimensional cube. The problems of the stated series include practically useful problems. Since the range of values for an integer computer variable can be considered integer values from a segment, if P ≠ NP, theorem 5 proves that any algorithm that solves these systems in the set of numbers of the integer type is nonpolynomial [6].

KW - integer point from a bounded domain belonging to the intersection of hyperplanes

KW - NP completeness

KW - system of linear Diophantine congruences

KW - system of linear Diophantine equations

UR - http://www.scopus.com/inward/record.url?scp=84976348945&partnerID=8YFLogxK

U2 - 10.3103/S1063454116020084

DO - 10.3103/S1063454116020084

M3 - Article

AN - SCOPUS:84976348945

VL - 49

SP - 111

EP - 114

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 2

ER -