INVESTIGADORES
PERRUCCI Daniel Roberto
artículos
Título:
Real roots of univariate polynomials and straight line programs
Autor/es:
DANIEL PERRUCCI; JUAN SABIA
Revista:
Journal of Discrete Algorithms
Editorial:
Elsevier
Referencias:
Año: 2007 vol. 5 p. 471 - 478
ISSN:
1570-8667
Resumen:
We give a new proof of the NP-hardness of deciding theexistence of real roots of an integer univariate polynomial encodedby a straight line program based on certain properties of theTchebychev polynomials. These techniques allow us to prove some new NP-hardness results related to real root approximation forpolynomials given by straight line programs.
