Un algoritmo para hallar soluciones de sistemas de ecuaciones e inecuaciones polinomiales

JERONIMO, GABRIELA; PERRUCCI, DANIEL; SABIA, JUAN

Mendoza

Congreso; LVIII Reunión anual de comunicaciones científicas de la Unión Matemática Argentina; 2008

Dada una combinación booleana de ecuaciones e inecuaciones polinomiales con coeficientes reales, una pregunta que puede formularse es si el conjunto que define en Rn es vacío o no (un caso particular de este problema es el de decidir si un sistema de ecuaciones e inecuaciones polinomiales tiene solución en Rn). Un problema que está estrechamente relacionado con esta pregunta es el de determinar, dada una lista de polinomios en R[x1,…,xn], cuáles son las condiciones de signo factibles definidas por esta lista. Una de las subrutinas básicas utilizadas en los algoritmos que trabajan en estos problemas (ver [Ren92], [BPR96], [BGHM01], [SS03] entre otros) consiste en hallar un conjunto finito que contenga un punto en cada una de las componentes conexas de un conjunto semialgebraico. En esta charla presentaremos un algoritmo probabilístico que, dada una familia de polinomios f1,…,fs en Q[x1,…,xn], calcula un conjunto finito de puntos (representado por una familia de resoluciones geométricas) que interseca a cada componente conexa de cada conjunto definido por igualdades y desigualdades no estrictas de estos polinomios a cero. El algoritmo extiende resultados previos (ver [JPS]), válidos bajo hipótesis de regularidad sobre los polinomios, al caso de familias arbitrarias. Las cotas de complejidad obtenidas mejoran las de los algoritmos conocidos que resuelven el mismo problema.   Referencias [BGHM01] B. Bank, M. Giusti, J. Heintz, G.M. Mbakop, Polar varieties and efficient real elimination. Math. Z. 238 (2001), No. 1, 115-144. [BPR96] S. Basu, R. Pollack, M-F. Roy, On the combinatorial and algebraic complexity of quantifier elimination, J. ACM, 43(6):1002-1045, 1996. [JPS] G. Jeronimo, D. Perrucci, J. Sabia, On sign conditions over real multivariate polynomials. Disponible en arXiv:0801.0586. [Ren92] J. Renegar, On the computational complexity and geometry of the first-order theory of the reals, J. Symbolic Comput. 13(3):255-352,1992. [SS03] M. Safey El Din, E. Schost, Polar varieties and computation of one point in each connected component of a smooth algebraic set, Proc. of the 2003 Internat. Symposium on Symbolic and Algebraic Computation, 224-231 (elect.), ACM, New York, 2003.