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

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

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

Аннотация

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.

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

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

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

Fingerprint Подробные сведения о темах исследования «NP-completeness conditions for consistency verification of some types of systems of linear Diophantine dis-equations». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать