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

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

Аннотация

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

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

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

Цитировать