NP- полные задачи о системах делимостей значений линейных выражений

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

Аннотация

Предметом данной статьи является исследование алгоритмической сложности подзадач задачи проверки совместности систем делимостей значений линейных выражений с неотрицательными коэффициентами в положительных целых числах. В общем случае не известно, принадлежит ли она классу {\bf NP}, но ранее было доказано что она принадлежит классу {\bf NEXPTIME}. В работе доказывается NP-полнота таких двух серий сужений этой задачи, что в первом из них делителем линейного выражения является число, а во втором сужении линейное выражение является делителем числа. Установлены такие значения параметров, при которых задачи являются NP-полными. Для м\'еньших значений параметра доказана принадлежность задач классу {\bf P}. Доказана NP-трудность частного случая общей задачи СОВМЕСТНАЯ ДЕЛИМОСТЬ ЛИНЕЙНЫХ МНОГОЧЛЕНОВ, в котором коэффициенты при переменных могут принимать значения только из множества $\{1,2\}$, а свободные члены линейных выражений могут принимать значения только из множества $\{1,5\}$. Полученные результаты могут послужить для выяснения алгоритмической сложности общей задачи. В разделе 1 доказано, что задача $\exists x_1\ldots x_n ~\&_{j=1}^m (L_j(x_1\ldots x_n)~|~K)$ NP-полна при $K\ge 4$ и не более трёх ненулевых коэффициентов при переменных в каждом полиноме и принадлежит классу {\bf P} при $0<K<4$. В разделе 2 исследована задача проверки совместности в целых числах из заданного невырожденного отрезка положительных целых чисел $[D,D']$, системы делимостей значений линейных полиномов с целыми коэффициентами на целое число $K$ $\exists x_1\ldots x_n (~\&_{i=1}^n x_i\in [D,D'] ~\&~ ~\&_{j=1}^m K~|~L_j(x_1\ldots x_n))$. Доказана её NP-полнота для любого $K\ge 3$. Если параметром задачи выбрать число ненулевых коэффициентов при переменных, задача является NP-полной уже при только двух ненулевых коэффициентах. В случае, когда не равен нулю только один коэффициент, задача находится в классе {\bf P}. \sloppy{ } В разделе 3 доказана NP-трудность задачи проверки совместности в положительных целых числах системы делимостей значений линейных полиномов на значения линейных полиномов $\exists x_1\ldots x_n ~\&_{j=1}^m (L_j(x_1\ldots x_n)~|~L'_j(x_1\ldots x_n))$ с коэффициентами при переменных из $\{1,2\}$ и свободными членами из $\{1,5\}$.
Переведенное названиеNP-COMPLETE PROBLEMS FOR SYSTEMS OF DIVISIBILITIES OF VALUES OF LINEAR POLYNOMIALS
Язык оригиналарусский
Страницы (с-по)236-246
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Том4(62)
Номер выпуска2
DOI
СостояниеОпубликовано - 2017

Предметные области Scopus

  • Математика (все)
  • Компьютерные науки (все)

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

  • система делимостей значений линейных выражений
  • NP-трудность
  • NP-полнота

Fingerprint Подробные сведения о темах исследования «NP- полные задачи о системах делимостей значений линейных выражений». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать