TY - JOUR

T1 - NP-complete problems for systems of Linear polynomial’s values divisibilities

AU - Kosovskii, N. K.

AU - Kosovskaya, T. M.

AU - Kosovskii, N. N.

AU - Starchak, M. R.

PY - 2017/4/1

Y1 - 2017/4/1

N2 - The paper studies the algorithmic complexity of subproblems for satisfiability in positive integers of simultaneous divisibility of linear polynomials with nonnegative coefficients. In the general case, it is not known whether this problem is in the class NP, but that it is in NEXPTIME is known. The NP-completeness of two series of restricted versions of this problem such that a divisor of a linear polynomial is a number in the first case, and a linear polynomial is a divisor of a number in the second case is proved in the paper. The parameters providing the NP-completeness of these problems have been established. Their membership in the class P has been proven for smaller values of these parameters. For the general problem SIMULTANEOUS DIVISIBILITY OF LINEAR POLYNOMIALS, NP-hardness has been proven for its particular case, when the coefficients of the polynomials are only from the set {1, 2} and constant terms are only from the set {1, 5}.

AB - The paper studies the algorithmic complexity of subproblems for satisfiability in positive integers of simultaneous divisibility of linear polynomials with nonnegative coefficients. In the general case, it is not known whether this problem is in the class NP, but that it is in NEXPTIME is known. The NP-completeness of two series of restricted versions of this problem such that a divisor of a linear polynomial is a number in the first case, and a linear polynomial is a divisor of a number in the second case is proved in the paper. The parameters providing the NP-completeness of these problems have been established. Their membership in the class P has been proven for smaller values of these parameters. For the general problem SIMULTANEOUS DIVISIBILITY OF LINEAR POLYNOMIALS, NP-hardness has been proven for its particular case, when the coefficients of the polynomials are only from the set {1, 2} and constant terms are only from the set {1, 5}.

KW - NP-completeness

KW - NP-hardness

KW - system of linear polynomial’s values divisibilities

UR - http://www.scopus.com/inward/record.url?scp=85021889789&partnerID=8YFLogxK

U2 - 10.3103/S1063454117020078

DO - 10.3103/S1063454117020078

M3 - Article

AN - SCOPUS:85021889789

VL - 50

SP - 145

EP - 152

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 2

ER -