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
id paperaa:paper_15708667_v5_n3_p471_Perrucci
record_format dspace
spelling paperaa:paper_15708667_v5_n3_p471_Perrucci2023-06-12T16:50:45Z Real roots of univariate polynomials and straight line programs J. Discrete Algorithms 2007;5(3):471-478 Perrucci, D. Sabia, J. 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 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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)
language Inglés
orig_language_str_mv eng
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
work_keys_str_mv AT perruccid realrootsofunivariatepolynomialsandstraightlineprograms
AT sabiaj realrootsofunivariatepolynomialsandstraightlineprograms
_version_ 1769810046134255616

Ejemplares similares