Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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. © 2006 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Real roots of univariate polynomials and straight line programs
Autor:Perrucci, D.; Sabia, J.
Filiación:Departamento de Matemática, FCEN, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Departamento de Ciencias Exactas, CBC, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
CONICET, Argentina
Palabras clave:Complexity; Real roots; Straight line program; Approximation theory; Computational complexity; Integer programming; Problem solving; Real roots; Straight line program; Polynomials
Año:2007
Volumen:5
Número:3
Página de inicio:471
Página de fin:478
DOI: http://dx.doi.org/10.1016/j.jda.2006.10.002
Título revista:Journal of Discrete Algorithms
Título revista abreviado:J. Discrete Algorithms
ISSN:15708667
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_15708667_v5_n3_p471_Perrucci.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15708667_v5_n3_p471_Perrucci

Referencias:

  • Bailey, D., Borwein, P., Plouffe, S., On the rapid computation of various polylogarithmic constants (1997) Math. Comp., 66, pp. 903-913
  • Garey, M., Johnson, D., (1979) Computers and Intractability, A Guide to the Theory of NP-Completeness, , W.H. Freeman and Company, New York
  • Hardy, G., Wright, E., (1960) An Introduction to the Theory of Numbers. fourth ed., , Oxford University Press, Oxford
  • Kincaid, D., Cheney, W., (1991) Numerical Analysis: Mathematics of Scientific Computing, , Brooks/Cole Publishing Company, Belmont, CA
  • Plaisted, D., New NP-hard and NP-complete polynomial and integer divisibility problems (1984) Theoret. Comput. Sci., 31, pp. 125-138
  • Richter-Gebert, J., Kortenkamp, U., Complexity issues in dynamic geometry (2002) Foundations of Computational Mathematics, Proceedings of the Smale Fest 2000, , Cucker F., and Maurice Rojas J. (Eds), World Scientific Also available as technical report TRB-2000/22, Freie
  • Rojas, M., Algebraic geometry over four rings and the frontier to tractability (2000) Contemporary Mathematics, 270, pp. 275-321. , Proceedings of a Conference on Hilbert's Tenth Problem and Related Subjects. invited paper. Denef J., Lipshitz L., Pheidas T., and Van Geel J. (Eds). University of Gent, November 1-5, 1999, AMS Press
  • Strassen, V., Vermeidung von Divisionen (1973) J. Reine Angew. Math., 264, pp. 182-202

Citas:

---------- APA ----------
Perrucci, D. & Sabia, J. (2007) . Real roots of univariate polynomials and straight line programs. Journal of Discrete Algorithms, 5(3), 471-478.
http://dx.doi.org/10.1016/j.jda.2006.10.002
---------- CHICAGO ----------
Perrucci, D., Sabia, J. "Real roots of univariate polynomials and straight line programs" . Journal of Discrete Algorithms 5, no. 3 (2007) : 471-478.
http://dx.doi.org/10.1016/j.jda.2006.10.002
---------- MLA ----------
Perrucci, D., Sabia, J. "Real roots of univariate polynomials and straight line programs" . Journal of Discrete Algorithms, vol. 5, no. 3, 2007, pp. 471-478.
http://dx.doi.org/10.1016/j.jda.2006.10.002
---------- VANCOUVER ----------
Perrucci, D., Sabia, J. Real roots of univariate polynomials and straight line programs. J. Discrete Algorithms. 2007;5(3):471-478.
http://dx.doi.org/10.1016/j.jda.2006.10.002