Sobre la complejidad de la resolución de sistemas de ecuaciones polinomiales y de la interpolación polinomial multivariada
La resolución de sistemas de ecuaciones polinomiales y la interpolación polinomialmultivariada se analizan desde el punto de vista algorítmico y de la complejidadcomputacional. Desde el punto de vista algorítmico se exhibe un algoritmo probabilístico queresuelve un sistema polinomial cuya complejidad bit es esencialmente cuadrática enel número de Bézout del sistema y lineal en su talla bit. Este algoritmo resuelve elsistema de entrada módulo un número primo p y aplica levantamiento p–ádico. Paraesto, se establecen una serie de resultados sobre la longitud bit de un primo “lucky” p,es decir un primo para el cual la reducción del sistema de entrada módulo p preservaciertas propiedades geométricas y algebraicas fundamentales del sistema original. Luego este algoritmo se aplica al problema de la interpolación polinomial cuando elconjunto de nodos está dado como el conjunto de ceros de un sistema polinomial,dando como resultado un procedimiento que calcula intepolantes de “bajo grado”. La complejidad bit de estos algoritmos es similar a la de los algoritmos que usanbases de Grobner o H–bases en el peor caso y en ciertos casos de interés prácticopuede resultar considerablemente menor. Desde el punto de vista de la complejidad computacional se demuestran cotasinferiores para la complejidad de los problemas de interpolación polinomial. Se introduceun nuevo modelo computacional para la interpolación de Hermite–Lagrangeque incluye clases no lineales de interpolantes. Este modelo incluye fenómenos decoalescencia y captura una gran variedad de conocidos problemas y algoritmos deinterpolación. En este contexto, se exhiben ejemplos de problemas de interpolacióncon clases no lineales de interpolantes cuya complejidad es intrínsecamente exponencial,mostrando que nuestro algoritmo para interpolación polinomial multivariada esesencialmente asintóticamente óptimo para los problemas seleccionados y que nadase gana admitiendo no linealidad.