On the computational hardness of testing square-freeness of sparse polynomials

摘要

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