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

GABRIELA JERONIMO; DANIEL PERRUCCI; JUAN SABIA

Mendoza, Pcia. de Mendoza

Congreso; LVIII Reunión de Comunicaciones Científicas de la UMA; 2008

UMA

Dada una combinación booleana de ecuaciones e inecuacionespolinomiales con coeficientes reales, una pregunta que puedeformularse es si el conjunto que define en R^n es vacío o no (un caso particular de este problema es el de decidir si unsistema de ecuaciones e inecuaciones polinomiales tiene soluciónen R^n). Un problema que está estrechamente relacionadocon esta pregunta es el de determinar, dada una lista de polinomiosen R[x1,...,xn], cuáles son las condiciones designo factibles definidas por esta lista.Una de las subrutinas básicas utilizadas en los algoritmos quetrabajan en estos problemas (ver [Ren92], [BPR96], [BGHM01], [SS03]entre otros) consiste en hallar un conjunto finito que contenga unpunto en cada una de las componentes conexas de un conjuntosemialgebraico.En esta charla presentaremos un algoritmo probabilístico que,dada una familia de polinomios f1,..., fs enQ[x1,..., xn], calcula un conjunto finito de puntos(representado por una familia de resoluciones geométricas queinterseca a cada componente conexa de cada conjunto definido porigualdades y desigualdades no estrictas de estos polinomios a cero.El algoritmo extiende resultados previos (ver [JPS]), válidos bajohipótesis de regularidad sobre los polinomios, al caso de familiasarbitrarias. Las cotas de complejidad obtenidas mejoran las de losalgoritmos conocidos que resuelven el mismo problema. (Trabajo enprogreso.)[BGHM01] B. Bank, M. Giusti, J. Heintz, G.M. Mbakop, Polarvarieties and efficient real elimination. Math. Z. 238 (2001), No.1, 115-144.[BPR96] S. Basu, R. Pollack, M-F. Roy, On the combinatorial andalgebraic 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 enarXiv:0801.0586.[Ren92] J. Renegar, On the computational complexity and geometryof the first-order theory of the reals,  J. Symbolic Comput.13(3):255--352, 1992.[SS03] M. Safey El Din, E. Schost, Polarvarieties and computation of one point in each connected componentof a smooth algebraic set, Proc. of the 2003 Internat. Symposium onSymbolic and Algebraic Computation, 224-231 (elect.), ACM, New York, 2003.