NP-complete problems for systems of Linear polynomial’s values divisibilities
| Autor: | Mikhail R. Starchak, N. K. Kosovskii, T. M. Kosovskaya, N. N. Kosovskii |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
NEXPTIME Series (mathematics) Divisor General Mathematics 010102 general mathematics Polynomial arithmetic Polynomial remainder theorem Divisibility rule 01 natural sciences 010305 fluids & plasmas Square-free polynomial Combinatorics 0103 physical sciences 0101 mathematics Mathematics |
| Zdroj: | Vestnik St. Petersburg University, Mathematics. 50:145-152 |
| ISSN: | 1934-7855 1063-4541 |
| DOI: | 10.3103/s1063454117020078 |
| Popis: | 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}. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink