Quantifier elimination in the theory of an algebraically-closed field

Publisher Website
Google Scholar
Abstract
In this paper we develop a fast parallel procedure for deciding when a set of multivariate polynomials with coefficients in an arbitrary field K have a common algebraic solution. Moreover, since the proposed algorithm is algebraic, it easily yields a procedure for quantifier elimination in the theory of an arbitrary algebraically closed field.More precisely, we show how to decide whether m polynomials in n variables, each of degree at most d, with coefficients in an arbitrary field K have a common zero in the algebraic closure of K, using sequential time (mn)&Ogr;(n)d&Ogr;(n)2), or parallel time &Ogr;(n3 log3 d log m) with (mn)&Ogr;(n)d&Ogr;(n)2) processors, in the operations of the coefficient field K. Using randomization, this may be improved to (mn)&Ogr;(1)d&Ogr;(n) time.In addition, the construction is used give a direct EXPSPACE algorithm for quantifier elimination in the theory of an algebraically-closed field, which runs in PSPACE or parallel polynomial time when restricted to formulas with a fixed number of alternations of quantifiers.

This publication has 0 references indexed in Scilit: