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

Результат исследований: Научные публикации в периодических изданияхстатья

Аннотация

В статье предлагаются две серии теретико-числовых задач с явно выделенными параметрами, касающиеся дизсравнений по модулю 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-полнота.

Цитировать