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