Sparse complex polynomials and polynomial reducibility

摘要

We show that certain problems involving sparse polynomials with integer coefficients are at least as hard as any problem in NP. These problems include determining the degree of the least common multiple of a set of such polynomials, and related problems. The proofs make use of a homomorphism from Boolean expressions over the predicate symbols {P1,…,Pn} onto divisors of the polynomial xN−1, where N is the product of the first n primes. Various combinatorial and number theoretic applications are also presented.