On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials

摘要

We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field IF)p of p elements is NP-hard. We also discuss some related open problems about sparse polynomials.