NP-completeness conditions for some types of systems of linear diophantine dis-equations consistency checking

Authors

  • Nikolai K. Kosovskii
  • Tatiana M. Kosovskaya
  • Nikolai N. Kosovskii

Abstract

В статье предлагаются три серии теоретико-числовых задач с явно выделенными параметрами, касающиеся систем диофантовых дизуравнений с решениями из заданной области. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна.Доказывается, что при любых m и m∗ (m < m∗ ) задача проверки совместности на отреpзке [m, m∗ ] системы линейных диофантовых дизуравнений, каждое из которых содержит ровно 3 переменные (даже если коэффициенты при них из {-1, 1}), NP-полна. Эта задача допуска-ет также и простую геометрическую интерпретацию о NP-полноте задачи проверки наличия внутри многомерного куба целочисленной точки, не покрытой заданными гиперплоскостями, высекающими на произвольных трёх осях равные отрезки и параллельными всем остальным осям.Если в системе линейных диофантовых дизуравнений каждое дизуравнение содержит ровно 2 переменные, задача остаётся NP-полной при условии, что справедливо неравенствоm∗ - m > 2.Также доказывается, что если решение системы линейных диофантовых дизуравнений, каждое из которых содержит ровно 3 переменные, ищется на области, заданной системой полиномиальных неравенств, содержащей n-мерный куб и содержащейся в n-мерном параллелепипеде, симметричном относительно начала координат, то задача проверки её совместности NP-полна. Библиогр. 15 назв.

Downloads

Download data is not yet available.

References

1. Косовский Н.К., Косовская Т.М., Косовский Н.Н. Условия NP-полноты проверки совместности нескольких видов систем линейных дизсравнений // Вестник С-Петерб. ун-та. Сер. 1. Математика. Механика. Астрономия. 2016. Т. 3(61). Вып. 1. С. 25-31.

2. Косовский Н.К., Косовская Т.М., Косовский Н.Н. Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых сравнений и уравнений // Вестник С-Петерб. ун-та. Сер. 1. Математика. Механика. Астрономия. 2016. Т. 3(61). Вып. 2. С. 196-201.

3. Clausen M., Fortenbacher A. Efficient Solution of Linear Diophantine Equations // J. Symbolic Computation. 1989. Vol. 8, issue 1-2. P. 201-216.

4. Вялый М.Н. Сложность вычислительных задач // Математическое просвещение. Сер. 3. Вып. 4. С. 81-114.

5. Aardal K., Hurkens C.A.J., Lenstra A.K. Solving a system of linear Diophantine equations with lower and upper bounds of the variables // Mathematics of operations research. 2000. Vol. 25, N 3. P. 427-442.

6. Шарая И.А. Строение допустимого множества решений интервальной линейной системы // Вычислительные технологии. 2005. Т. 10, №5. С. 103-119.

7. Шарая И.А. Метод граничных интервалов для визуализации полиэдральных множеств решений // Вычислительные технологии. 2015. Т. 20, №1. С. 75-103.

8. Lechner A., Ouaknine J., Worrell J. On the Complexity of Linear Arithmetic with Divisibility // Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). 2015. P. 667-676.

9. Кривий С.Л. Лiнiйнi дiофантовi обмеження та їх застосування. Київ: Видавничий дiм «Букрек», 2015. 224 с.

10. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

11. Lagaris J.C. The computational complexity of simultaneous Diophantine approximation problems // SIAM Journal on Computing. 1985. Vol. 14. P. 196-209.

12. Схрейвер А. Теория линейного и целочисленного программирования. Т. 2. М.: Мир, 1991.

13. Косовская Т.М., Косовский Н.К. О числе шагов получения булевого решения у полиномиальных сравнений и у систем из них // Вестник С-Петерб. ун-та. Сер. 1. Математика. Механика. Астрономия. 2007. Вып. 3. С. 82-90.

14. Турчин В.Ф. Рефал-5. Руководство по программированию и справочник. URL: http://www.refal.net/rf5_frm.htm (дата обращения: 05.06.2016).

15. Косовский Н.К., Косовский Н.Н. NP-полнота задачи проверки совместности в отрезке целых чисел системы целочисленных линейных уравнений и дизуравнений // Дискретные модели в теории управляющих систем: IX Международная конференция, Москва и Подмосковье, 20- 22 мая 2015 г.: Труды / отв. ред. В. Б. Алексеев, Д. С. Романов, Б. Р. Данилов. М.: МАКС-Пресс, 2015. С. 123-125.

Downloads

Published

2020-08-20

How to Cite

Kosovskii, N. K., Kosovskaya, T. M., & Kosovskii, . N. N. (2020). NP-completeness conditions for some types of systems of linear diophantine dis-equations consistency checking. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 3(3), 408–414. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/8686

Issue

Vol. 3 No. 3 (2016)

Section

Mathematics

License

Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.