Some polynomial and integer divisibility problems are NP-HARD

Abstract

In an earlier paper [1], the author showed that certain problems involving sparse polynomials and integers are NP-hard. In this paper we show that many related problems are also NP-hard. In addition, we exhibit some new NP-complete problems. Most of the new results concern problems in which the nondeterminism is "hidden". That is, the problems are not explicitly stated in terms of one of a number of possibilities being true. Furthermore, most of these problems are in the areas of number theory or the theory of functions of a complex variable. Thus there is a rich mathematical theory that can be brought to bear. These results therefore introduce a class of NP-hard and NP-complete problems different from those known previously.