Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизуравнений

Авторы

  • Николай Кириллович Косовский
  • Татьяна Матвеевна Косовская
  • Николай Николаевич Косовский

Аннотация

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

Скачивания

Данные скачивания пока недоступны.

Библиографические ссылки

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.

Загрузки

Опубликован

20.08.2020

Как цитировать

Косовский , Н. К., Косовская , Т. М., & Косовский , Н. Н. (2020). Условия NP-полноты проверки совместности нескольких видов систем линейных диофантовых дизуравнений. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 3(3), 408–414. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/8686

Выпуск

Том 3 № 3 (2016)

Раздел

Математика

Лицензия

Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.

Наиболее читаемые статьи этого автора (авторов)