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

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

Аннотация

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}.

Язык оригиналаанглийский
Страницы (с-по)145-152
Число страниц8
ЖурналVestnik St. Petersburg University: Mathematics
Том50
Номер выпуска2
DOI
СостояниеОпубликовано - 1 апр 2017

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

  • Математика (все)

Fingerprint Подробные сведения о темах исследования «NP-complete problems for systems of Linear polynomial’s values divisibilities». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать