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

• Autores: Mikel Aldaz Zaragüeta
• Directores de la Tesis: José Luis Montaña Arnaiz (dir. tes.) , Luis Miguel Pardo Vasallo (dir. tes.)
• Lectura: En la Universidad Pública de Navarra ( España ) en 1999
• Idioma: español
• Tribunal Calificador de la Tesis: Tomás Jesús Recio Muñiz (presid.) , José Ramón Garitagoitia Padrones (secret.) , Marc Giusti (voc.) , Michel Lickteig Thomas (voc.) , Juan Llovet Verdugo (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.