Resumen de Cotas inferiores para problemas de evaluación en teoría de la complejidad algebraica
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.
