CONICET | Buscador de Institutos y Recursos Humanos

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 R^n 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 R^n. Un problema que está estrechamente relacionado con esta pregunta es el de determinar, dada una lista de polinomios en R[x_1,...,x_n], 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 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 finita de polinomios, calcula un conjunto finito de puntos (representado por una familia de resoluciones geométricas) que interseca a cada componente conexa de cada conjunto definido porigualdades y desigualdades no estrictas de estos polinomios a cero.El algoritmo extiende resultados previos, 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.

enviar mensaje