NP-полные задачи о системах делимостей значений линейных выражений

Авторы

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

Аннотация

Целью данной статьи является исследование алгоритмической сложности подзадач задачи проверки совместности систем делимостей значений линейных выражений с неотрицательными коэффициентами в положительных целых числах. В общем случае не известно, принадлежит ли она классу NP, но известна ее принадлежность классу NEXPTIME. В работе доказывается NP-полнота двух серий сужений этой задачи, что в первом из них делителем линейного выражения является число, а во втором сужении линейное выражение является делителем числа. Установлены значения параметров, при которых задачи являются NP-полными. Для меньших значений параметра доказана принадлежность задач классу P. Доказана NP-трудность частного случая общей задачи СОВМЕСТНАЯ ДЕЛИМОСТЬ ЛИНЕЙНЫХ МНОГОЧЛЕНОВ, в котором коэффициенты при переменных могут принимать значения только из множества {1, 2}, а свободные члены линейных выражений - только измножества {1, 5}. Библиогр. 13 назв.

Скачивания

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

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

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

2. Lipshitz L. Some remarks on the Diophantine problem for addition and divisibility // Bull. Soc. Math. Belg. Ser. B. 1981. Vol. 33, issue 1. P. 41-52.

3. Lipshitz L. The Diophantine problem for addition and divisibility // Transactions of the American Mathematical Society. 1976. Vol. 235. P. 271-283.

4. Бельтюков А.П. Разрешимость универсальной теории натуральных чисел со сложением и делимостью // Записки научных семинаров ЛОМИ. 1975. Т. 60. С. 15-28.

5. Haase C. On the complexity of model checking counter automata. Ph.D. Thesis, University of Oxford, 2012.

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

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

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

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

10. Schaefer T.J. The complexity of satisfiability problems // Proceedings 10th Symposium on Theory of Computing, ACM Press. 1978. P. 216-226.

11. Adleman L., Manders K. Reducibility, randomness and intractability // Proceedings of the 9th Annual ACM Symposium on Theory of Computing. 1977. P. 151-163.

12. Cohen H. A Course in Computational Algebraic Number Theory, ser. Graduate Texts in Mathematics. Vol. 138. Springer-Verlag, 1993.

13. Lagarias J.C. The computational complexity of simultaneous diophantine approximation problems // 23th Annual Symposium on Foundations of Computer Science, IEEE. New York, 1982. P. 32-39.

Загрузки

Опубликован

20.08.2020

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

Косовский, Н. К., Косовская, Т. М., Косовский, Н. Н., & Старчак , М. Р. (2020). NP-полные задачи о системах делимостей значений линейных выражений. Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия, 4(2), 236–246. извлечено от https://math-mech-astr-journal.spbu.ru/article/view/8608

Выпуск

Том 4 № 2 (2017)

Раздел

Математика

Лицензия

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

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