Sobre el problema 17 de smaleteoría de la intersección y geometría integral

Laburpena

En el año 2000, el ganador de la medalla Fields Stephen Smale propuso 18 problemas de matemáticas para el siglo XXI, El número 17 de esos problemas pregunta sobre la existencia de un algoritmo que aproxime soluciones de sistemas de ecuaciones multivariados con coeficientes complejos, en un tiempo polilnomial en media en la talla del input. En esta tesis se expone la primera solución probabilística a este problema. Esto es, se describe un algoritmo con la propiedad de que, dado un sistema de ecuaciones polinomiales, encuentra una solución aproximada en tiempo polinomial, aceptando una pequeña probabilidad de error que se puede ajustar en función de las necesidades y recursos. Como paso previo a la resolución de dicho problema, se introducen numerosos resultados intermedios que analizan el comportamiento promedio de las cantidades asociadas a la complejidad de resolución, así como a la estabilidad del problema. En particular, se obtienen cotas de volúmenes de tubos y de intersección de tubos con variedades que permiten estimar mediante una técnica general todos los problemas del numero de condicionamiento lineal y no lineal, en un contexto ampliamente generalizado. Los resultados son estudiados tanto desde un punto de vista de computación continua como desde una perspectiva discreta, aportados para este último objetivo las cotas más finas conocidas hasta el momento de principios de transferencia de resultados continuos a discretos, principalmente en el caso de problemas definidos de modo proyectivo. También se muestran otros resultados puramente geométricos y algebraicos con interés propio, y se estiman otras cantidades auxiliares de cierta relevancia, como la norma media de las soluciones de un sistema de ecuaciones polinomiales con coeficientes complejos.