Details

Autor(en) / Beteiligte

• Basu, Saugata
• Pollack, Richard
• Roy, Marie-Françoise

Titel

On the combinatorial and algebraic complexity of quantifier elimination

Ist Teil von

• Journal of the ACM, 1996-11, Vol.43 (6), p.1002-1045

Ort / Verlag

New York, NY: ACM

Erscheinungsjahr

1996

Link zum Volltext

Quelle

ACM Digital Library

Beschreibungen/Notizen

• In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data. A new feature of this algorithm is that the role of the algebraic part (the dependence on the degrees of the imput polynomials) and the combinatorial part (the dependence on the number of polynomials) are sparated. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that is output, are independent of the number of input polynomials. As special cases of this algorithm new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields, are obtained.