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

Результат исследований: Научные публикации в периодических изданияхстатья

3 Цитирования (Scopus)

Аннотация

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].

Язык оригиналаанглийский
Страницы (с-по)111-114
Число страниц4
ЖурналVestnik St. Petersburg University: Mathematics
Том49
Номер выпуска2
DOI
СостояниеОпубликовано - 1 апр 2016

Предметные области Scopus

  • Математика (все)

Fingerprint Подробные сведения о темах исследования «NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine congruences and equations». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать