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

Full description

Saved in:
Bibliographic Details
Published in:Vestnik, St. Petersburg University. Mathematics St. Petersburg University. Mathematics, 2017-04, Vol.50 (2), p.145-152
Main Authors: Kosovskii, N. K., Kosovskaya, T. M., Kosovskii, N. N., Starchak, M. R.
Format: Article
Language:English
Subjects:
Analysis
Completeness
Complexity
Hardness
Integers
Mathematics
Mathematics and Statistics
Numbers
Polynomials
Surface hardness
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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}.
ISSN:1063-4541
1934-7855
DOI:10.3103/S1063454117020078