NP-complete problems for systems of divisibilities of values of linear polynomials

Authors

  • Nikolay K. Kosovskii
  • Tatiana M. Kosovskaya
  • Nikolay N. Kosovskii
  • Mikhail R. Starchak

Abstract

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

Downloads

Download data is not yet available.

References

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.

Downloads

Published

2020-08-20

How to Cite

Kosovskii, N. K., Kosovskaya, T. M., Kosovskii, N. N., & Starchak, M. R. (2020). NP-complete problems for systems of divisibilities of values of linear polynomials. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 4(2), 236–246. Retrieved from https://math-mech-astr-journal.spbu.ru/article/view/8608

Issue

Vol. 4 No. 2 (2017)

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.

Most read articles by the same author(s)