Some NP-Hard Problems for the Simultaneous Coprimeness of Values of Linear Polynomials
The algorithmic-time complexity of some problems connected with linear polynomials and coprimeness relation on natural numbers is under consideration in the paper. We regard two easily stated problems. The first one is on the consistency in natural numbers from the interval of a linear coprimeness system. This problem is proved to be NP-complete. The second one is on the consistency in natural numbers of a linear coprimeness and discoprimeness system for polynomials with not greater than one non-zero coefficient. This problem is proved to be NP-hard. Then the complexity of some existential theories of natural numbers with coprimeness is considered. These theories are in some sense intermediate between the existential Presburger arithmetic and the existential Presburger arithmetic with divisibility. In a form of corollaries from the theorems of the second section we prove NP-hardness of the decision problem for the existential theories of natural numbers for coprimeness with addition and for coprimeness with successor function. In the conclusion section we give some remarks on the NP membership of the latter problem.
