В статье предлагаются две серии теретико-числовых задач с явно выделенными параметрами, касающиеся дизсравнений по модулю m. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна. Доказывается, что при всяком m>2 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 3 переменные (даже если коэффициенты при них из {-1,1}), NP-полна. Также доказывается, что при всяком m>3 задача проверки совместности системы линейных дизсравнений по модулю m, каждое из которых содержит ровно 2 переменные, NP-полна. Если P \neq NP, то формулировки доказанных теорем не могут быть изменены путём замены термина > на термин >.
Язык оригиналарусский
Страницы (с-по)196 — 201.
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ
Том3(.61)
Номер выпуска1
СостояниеОпубликовано - 2016
Опубликовано для внешнего пользованияДа

    Области исследований

  • система линейных диофантовых дизсравнений, NP-полнота.

ID: 7591689