|
|||||
|
|
Real roots of univariate polynomials and straight line programs |
|
| Authors: | Daniel Perrucci Juan Sabia |
| Institution: | aDepartamento de Matemática, FCEN, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina;bDepartamento de Ciencias Exactas, CBC, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina;cCONICET, Argentina |
| Abstract: | 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. |
| Keywords: | Real roots Straight line program Complexity |
| 本文献已被 ScienceDirect 等数据库收录！ | |