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
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
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15708667_v5_n3_p471_Perrucci_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_15708667_v5_n3_p471_Perrucci_oai
record_format dspace
spelling I28-R145-paper_15708667_v5_n3_p471_Perrucci_oai2024-08-16 Perrucci, D. Sabia, J. 2007 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. application/pdf http://hdl.handle.net/20.500.12110/paper_15708667_v5_n3_p471_Perrucci info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar J. Discrete Algorithms 2007;5(3):471-478 Complexity Real roots Straight line program Approximation theory Computational complexity Integer programming Problem solving Real roots Straight line program Polynomials Real roots of univariate polynomials and straight line programs info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15708667_v5_n3_p471_Perrucci_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (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, D.
Sabia, J.
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.
format Artículo
Artículo
publishedVersion
author Perrucci, D.
Sabia, J.
author_facet Perrucci, D.
Sabia, J.
author_sort Perrucci, D.
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 http://hdl.handle.net/20.500.12110/paper_15708667_v5_n3_p471_Perrucci
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_15708667_v5_n3_p471_Perrucci_oai
work_keys_str_mv AT perruccid realrootsofunivariatepolynomialsandstraightlineprograms
AT sabiaj realrootsofunivariatepolynomialsandstraightlineprograms
_version_ 1809356930393571328

Ejemplares similares