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: JOUR
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 todo:paper_15708667_v5_n3_p471_Perrucci
record_format dspace
spelling todo:paper_15708667_v5_n3_p471_Perrucci2023-10-03T16:26:52Z Real roots of univariate polynomials and straight line programs 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. JOUR 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)
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 JOUR
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
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_ 1807318206549852160

Ejemplares similares