New NP-hard and NP-complete polynomial and integer divisibility problems
David A. Plaisted · 1977
Abstract We show that some problems involving sparse polynomials are NP-hard. For example, it is NP-hard to determine if a sparse polynomial has a root of modulus 1, and it is NP-hard to decide if two sparse polynomials are not relatively prime. Also, we show that a divisibility problem involving an unbounded number of sparse polynomials is NP-complete using a theorem of Linnik concerning the distribution of primes in arithmetic sequences. From these results it follows that certain problems involving inequalities, recurrence relations, differential equations, and eigenvalues of sparse matrices are NP-hard. Problems involving divisibility properties of two sparse polynomials, divisibility of sparse binary numbers and ring homomorphisms are also NP-hard.