Tarski-Seidenberg principle plays a key role in many applications and algorithm of computer algebra. Moreover it is constructive, and some very efficient quantifier elimination algorithms appeared recently. However, Tarski-Seidenberg principle is wrong for first-order theories involving some real analytic functions (e.g. an exponential function). In this case a weaker statement is sometimes true, a possibility to eliminate one sort of quantifiers (either ∀ or ∃). We construct a new algorithm for a cylindrical cell decomposition of a closed cube In ⊄ Rn compatible with a semianalytic subset S ⊄ In, defined by Pfaffian functions. In particular the algorithm is able to eliminate one sort of quantifiers from a first-order formula. The complexity bound of the algorithm is doubly exponential in n2.

Let F be an algebraically closed field of zero characteristic, a polynomial @@@@ ∈ F[X1, … , Xn have a multiplicative complexity r and ƒ1, … ƒk ∈ F[X1, … , Xn] be some polynomials of degrees not exceeding d, such that @@@@ = ƒ1 = ··· = ƒk = 0 has a finite number of roots. We show that the number of possible distinct vectors of multiplicities of these roots is small when r, d and k are small. As technical tools we design algorithms which produce Gröbner bases and vectors of multiplicities of the roots for a parametric zero-dimensional system. The complexities of these algorithms are singly exponential. We also describe an algorithm for parametric absolute factorization of multivariate polynomials. This algorithm has subexponential complexity in the case of a small (relative to the number of variables) degree of the polynomials.

An algorithm Is constructed for computing the local dimension of a ocmialgcbmlc set V at a given point z E V. Let V be deflned by a t;ystcm of h inequalities of the form f 2 0 with f E R[Xl,,,., X,], de&) < d, and x E V belong to a stratum of codimcnoion Is in V of a Whitney stratification of V.The algorhhm computes the local dimension dim,(V) with the complexity (Cld) '(@), If 1 = rnax=Bv I,, and for every connectedcomponent the local dimension is the same at each point, then the algorhhm computes the dimension of every connected component with complexity (t13) o(Bn), In the case of a real algebraic variety de- fined by a system of equations the complexity of the algorithm is leas Lhnn d'("").When 1 is fixed, like in the case of a smooth V, lhc complcxily bounds are (kd)'(") and do(") respectively.

We describe an algorithm for producing the smallest complex algebralc variety containing a given semi-algebraic set S, and all the irreducible components of S. Let S be defined by s polynomials of degrees less than d with integer coefficients of bit lengths less than A4.Then the complexity of the algorithm is bounded from above by a polynomial in M, Sn, dn'.The degree of the complexification is less than sndo 'n), while the degrees of polynomials defining the complexification and irreducible components are less than do(n) 1

We introduce a new method of proving lower bounds on the depth of algebraic decision trees of degree d and apply it to prove a lower bound /spl Omega/(log N) for testing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N>(nd)/sup /spl Omega//(n). This weakens considerably the restriction on N previously imposed by the authors and opens a possibility to apply the bound to some naturally appearing polyhedra.

We consider computation trees which admit as gate functions along with the usual arithmetic operations also algebraic or transcendental functions like exp, log, sin, square root (defined in the relevant domains) or much more general, Pfaffian functions. A new method for proving lower bounds on the depth of these trees is developed which allows to prove a lower bound /spl Omega/(/spl radic/(log N)) for testing membership to a convex polyhedron with N facets of all dimensions, provided that N is large enough. This method differs essentially from the previous approaches adopted for algebraic computation trees.>

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \\Omega\\Gammand/ N) for testing membership to a convex polyhedron having N facets of all dimensions, provided that N is large enough. This bound apparently does not follow from the methods developed by M. Ben-Or, A. Bjorner, L. Lovasz, and A. Yao ([B 83], [BLY 92]) because the topological invariants used in these methods become trivial for a convex polyhedra. Departments of Computer Science and Mathematics, Penn State University, University Park, PA 16802, Email: [email protected]. Supported in part by the Volkswagen-- Stiftung. y Department of Computer Science, University of Bonn, 53117 Bonn, and the International Computer Science Institute, Berkeley, California. Research supported in part by DFG Grant KA 673/4--1, by the ESPRIT BR Grants 7097 and ECUS030, and by the Volkswagen-Stiftung. Email: [email protected] z Departments of Computer Science and Mathemat...