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

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

Аннотация

В статье предлагаются три серии теретико-числовых задач с явно выделенными параметрами, касающиеся систем диофантовых дизуравнений с решениями из заданной области. Доказываются ограничения на параметры, при выполнении которых любая задача каждой серии NP-полна. Доказывается, что при любых $m$ и $m'$ ($m2$. Также доказывается, что если решение системы линейных диофантовых ди
Язык оригиналарусский
Страницы (с-по)408–414
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 1: МАТЕМАТИКА, МЕХАНИКА, АСТРОНОМИЯ
Том3 (61)
Номер выпуска3
СостояниеОпубликовано - 2016
Опубликовано для внешнего пользованияДа

Ключевые слова

  • система линейных диофантовых дизуравнений
  • принадлежность целочисленной точки из ограниченной области пересечению гиперплоскостей
  • NP-полнота.

Цитировать