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
id paper:paper_15708667_v5_n3_p471_Perrucci
record_format dspace
spelling paper:paper_15708667_v5_n3_p471_Perrucci2023-06-08T16:24:15Z Real roots of univariate polynomials and straight line programs Perrucci, Daniel Sabia, Juan Vicente Rafael Complexity Real roots Straight line program Approximation theory Computational complexity Integer programming Problem solving Real roots Straight line program Polynomials 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. Fil:Perrucci, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Sabia, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2007 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
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Complexity
Real roots
Straight line program
Approximation theory
Computational complexity
Integer programming
Problem solving
Real roots
Straight line program
Polynomials
spellingShingle Complexity
Real roots
Straight line program
Approximation theory
Computational complexity
Integer programming
Problem solving
Real roots
Straight line program
Polynomials
Perrucci, Daniel
Sabia, Juan Vicente Rafael
Real roots of univariate polynomials and straight line programs
topic_facet Complexity
Real roots
Straight line program
Approximation theory
Computational complexity
Integer programming
Problem solving
Real roots
Straight line program
Polynomials
description 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.
author Perrucci, Daniel
Sabia, Juan Vicente Rafael
author_facet Perrucci, Daniel
Sabia, Juan Vicente Rafael
author_sort Perrucci, Daniel
title Real roots of univariate polynomials and straight line programs
title_short Real roots of univariate polynomials and straight line programs
title_full Real roots of univariate polynomials and straight line programs
title_fullStr Real roots of univariate polynomials and straight line programs
title_full_unstemmed Real roots of univariate polynomials and straight line programs
title_sort real roots of univariate polynomials and straight line programs
publishDate 2007
url 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
work_keys_str_mv AT perruccidaniel realrootsofunivariatepolynomialsandstraightlineprograms
AT sabiajuanvicenterafael realrootsofunivariatepolynomialsandstraightlineprograms
_version_ 1768545023453822976

Ejemplares similares