Complejidad de algoritmos en polinomios dados por slp

DANIEL PERRUCCI; JUAN SABIA

Salta, Pcia. de Salta

Congreso; LV Reunión de Comunicaciones Científicas de la UMA; 2005

UMA

Uno de los problemas principales en geometría algebraica real esel de decidir si un polinomio tiene raíces reales o no. Cuando lospolinomios involucrados tienen una estructura particular, se intentan buscar algoritmos más eficientes que resuelvan el problema en estos casos particulares. En esta comunicación, damos una nueva demostración de que el problema de decidir si un polinomio dadopor un cálculo de evaluación (o straight-line program, o slp) es NP-Hard. También probamos que algunos problemas relacionados ala aproximación de raíces de polinomios dados por un slp tambiénson NP-Hard. Nuestras demostraciones se basan en un método   que D. Plaisted ([1]) realizó con polinomios ciclotómicos en otrocontexto, adaptado a los polinomios de Tchevychev.[1] D. Plaisted, New NP-Hard and NP-Complete polynomial andinteger divisibility problems, Theoretical Computer Science (1984),vol. 31, 125-138.