Real roots of univariate polynomials and straight line programs

We give a new proof of the NP-hardness of deciding the existence of real roots of an integer univariate polynomial encoded by a straight line program based on certain properties of the Tchebychev polynomials. These techniques allow us to prove some new NP-hardness results related to real root approx...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Perrucci, Daniel, Sabia, Juan Vicente Rafael
Publicado: 2007
Materias:
Complexity
Real roots
Straight line program
Approximation theory
Computational complexity
Integer programming
Problem solving
Polynomials
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15708667_v5_n3_p471_Perrucci
http://hdl.handle.net/20.500.12110/paper_15708667_v5_n3_p471_Perrucci
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares