Conjuntos definibles por polinomios en varias variables

GABRIELA JERONIMO

"Premio Presidencia de la Nación 1998"- Foro interdisciplinario de estudiantes excelentes

Año: 1999; p. 873 - 917

El capítulo se centra en el estudio de la complejidad de la reescritura de una fórmula de primer orden sobre un cuerpo algebraicamente cerrado, sin cuantificadores, en forma normal disyuntiva. A partir de una estimación precisa de la cantidad de conjuntos que pueden definirse por igualdades y desigualdades de una familia fija de polinomios a cero, se muestra que los algoritmos conocidos para resolver el problema son esencialmente óptimos. Asimismo se analizan las consecuencias de los resultados obtenidos en el estudio de la complejidad de la eliminación de cuantificadores en esa teoría.