TY - JOUR

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

AU - Косовский, Н.К.

AU - Косовская, Т.М.

AU - Косовский, Н.Н.

AU - Старчак, М.Р.

N1 - Косовский Н.К., Косовская Т.М., Косовский Н.Н., Старчак М.Р. NP- полные задачи о системах делимостей значений линейных выражений // Вестник СПбГУ. Математика. Механика. Астрономия. 2017. Т. 4 (62). Вып. 2. С. 236–246.

PY - 2017

Y1 - 2017

N2 - Предметом данной статьи является исследование алгоритмической сложности подзадач задачи проверки совместности систем делимостей значений линейных выражений с неотрицательными коэффициентами в положительных целых числах. В общем случае не известно, принадлежит ли она классу {\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\}$.

AB - Предметом данной статьи является исследование алгоритмической сложности подзадач задачи проверки совместности систем делимостей значений линейных выражений с неотрицательными коэффициентами в положительных целых числах. В общем случае не известно, принадлежит ли она классу {\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\}$.

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

KW - NP-трудность

KW - NP-полнота

KW - system of divisibilities of values of linear polynomials

KW - NP-hardness

KW - NP-completeness

UR - http://vestnik.spbu.ru/html17/s01/s01v2/07.pdf

U2 - DOI: 10.21638/11701/spbu01.2017.207

DO - DOI: 10.21638/11701/spbu01.2017.207

M3 - статья

VL - 4(62)

SP - 236

EP - 246

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 2

ER -