NP-completeness conditions for some types of systems of linear diophantine dis-equations consistency checking
Nikolai K. Kosovskii, Tatiana Matveevna Kosovskaya, Nikolay N. Kosovskii · Vestnik of Saint Petersburg University Mathematics Mechanics Astronomy · 2016
УДК 510.51 Вестник СПбГУ.Сер. 1. Т. 3 (61).2016.Вып. 3 УСЛОВИЯ NP-ПОЛНОТЫ ПРОВЕРКИ СОВМЕСТНОСТИ НЕСКОЛЬКИХ ВИДОВ СИСТЕМ ЛИНЕЙНЫХ ДИОФАНТОВЫХ ДИЗУРАВНЕНИЙ Н. К. Косовский, Т. М. Косовская, Н. Н. Косовский Санкт-Петербургский государственный университет, Российская Федерация, 199034, Санкт-Петербург, Университетская наб., 7-9 В статье предлагаются три серии теоретико-числовых задач с явно выделенными параметрами, касающиеся систем диофантовых дизуравнений с решениями из заданной области.Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна.Доказывается, что при любых m и m (m 2.Также доказывается, что если решение системы линейных диофантовых дизуравнений, каждое из которых содержит ровно 3 переменные, ищется на области, заданной системой полиномиальных неравенств, содержащей n-мерный куб и содержащейся в n-мерном параллелепипеде, симметричном относительно начала координат, то задача проверки её совместности NP-полна.Библиогр.15 назв.