Cotas inferiores para problemas de evaluación en teoría de la complejidad algebraica

Resumo

En esta tesis se estudia la complejidad computacional del problema de la evaluación de polinomios y funciones racionales en un punto arbitrario, Los resultados más destacables de entre los presentados en la memoria de tesis son: * Desarrollo de un modelo de computación que tiene en cuenta conjuntamente. - En la forma de un "Tradroff" los recursos de tiempo y espacio empleados por los algoritmos de evaluación de polinomios y funciones racionales. Se presenta un teorema de representación para las computaciones que se realizan con recursos de tiempo y espacio limitados y se obtienen cotas inferiores genéricas para la medida de complejidad dada por el "Tradeoff" espacio-tiempo. * Dos nuevos métodos para la obtención de cotas inferiores para la complejidad de evaluación de familias de polinomios espcíficas: - Método de la altura de la flora. - Método combinatorio. Una característica de ambos métodos es que pueden ser aplicados a polonomios que sólo tienen raíces enteras, lo que la ha permitido por vez primera obtener cotas inferiores significativas para familias de polinomios de este tipo. * Un nuevo criterio de transcendencia para series formales de potencias.