Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-027 | 17th July 1999 00:00

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

RSS-Feed




TR99-027
Authors: Marek Karpinski, Igor E. Shparlinski
Publication: 19th July 1999 17:10
Downloads: 1149
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint