Real roots of univariate polynomials and straight line programs

Mostrar todas las versiones(3)

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, D., Sabia, J.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: 2007
Materias:
Complexity
Real roots
Straight line program
Approximation theory
Computational complexity
Integer programming
Problem solving
Polynomials
Acceso en línea: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
Descripción
Sumario: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 approximation for polynomials given by straight line programs. © 2006 Elsevier B.V. All rights reserved.

Ejemplares similares