In this paper we obtain an effective algorithm for quantifier elimination over algebraically closed fields: For every effective infinite integral domain k, closed under the extraction of pth roots when the characteristic p of k is positive, and every prenex formula phi with r blocks of quantifiers involving s polynomials F-1,...,F-s is an element of k[X-1,...,X-n] encoded in dense form, there exists a well-parallelizable algorithm without divisions whose output is a quantifier-free formula equivalent to phi. The sequential complexity of this algorithm is bounded by O(phi) + D-(O(n)r), where phi is the length of phi and D greater than or equal to n is an upper bound for 1 + Sigma(i=1)(s) degF(i), and the polynomials in the output are encoded by means of a straight line program. The complexity bound obtained is better than the bounds of the known elimination algorithms, which are of the type phi.D-ncr, where c greater than or equal to 2 is a constant. This becomes notorious when r = 1 (i.e., when there is only one block of quantifiers): the complexity bounds known up to now are not less than D-n2, while our bound is D-O(n). Moreover, in the particular case that there is only one block of existential quantifiers and the input polynomials are given by a straight line program, we construct an elimination algorithm with even better bounds which depend on the length of this straight line program: Given a formula of the type There Exists x(n - m + 1,...,) There Exists x(n): F-1(x(1),...,x(n)) = 0 boolean AND ... boolean AND F-s(x(1),...x(n)) = 0 boolean AND G(1) (x(1),..., x(n)) not equal 0 boolean AND ... boolean AND G(s') (x(1),..., x(n)) not equal 0 where F-1,..., F-s is an element of k[X-1,...,X-n] are polynomials whose degrees in the m variables Xn - m + 1,...,X-n are bounded by an integer d greater than or equal to m and G(1),...,G(s') is an element of k[X-1,...,X-n] are polynomials whose degrees in the same variables are bounded by an integer delta, this algorithm eliminates quantifiers in time L-2.(s.s'.delta)(O(1).)d(O(m)), where L is the length of the straight line program that encodes F-1,..., F-s, G(1),..., G(s'). Finally, we construct a fast algorithm to compute the Chow Form of an irreducible projective variety. The construction of all the algorithms mentioned above relies on a preprocessing whose cost exceedes the complexity classes considered (they are based on the construction of correct test sequences). In this sense, our algorithms are non-uniform but may be considered uniform as randomized algorithms (choosing the correct test sequences randomly). (C) 1998 Elsevier Science B.V. All rights reserved. [References: 41]
展开▼
