Algoritmos y conjuntos semialgebraicos

DANIEL PERRUCCI

Montevideo, Uruguay

Congreso; XVII Encuentro Rioplatense de Álgebra y Geometría Algebraica; 2007

Una de las preguntas fundamentales en geometría algebraicareal efectiva consiste en determinar si un conjunto definido enR^n por una familia de igualdades y desiguadades depolinomios con coeficientes reales es vacío o no. Esteproblema puede verse como un caso particular del problema de laeliminación de cuantificadores en la teoría de primer ordensobre los reales. Los algoritmos más eficientes conocidos paraeliminación de cuantificadores se basan en procedimientos parael cálculo de un punto en cada componente conexa de losconjuntos determinados por cada condición de signo definida poruna familia finita de polinomios. En esta charla presentaremos unposible acercamiento a este último problema. Describiremosun algoritmo para el cálculo, bajo ciertas hipótesis, de unconjunto finito con al menos un punto en la clausura de cada unade estas componentes conexas, que mejora las complejidadesconocidas. Este conjunto finito permite, a su vez, listar todaslas condiciones de signo factibles.