ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.4.2. <s> In this paper we apply for the first time a new method for multivariate equation solving which was developed in \cite{gh1}, \cite{gh2}, \cite{gh3} for complex root determination to the {\em real} case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm of \cite{gh1}, \cite{gh2}, \cite{gh3} yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem--adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in non-uniform sequential time that is {\em polynomial} in the length of the input (given in straight--line program representation) and an adequately defined {\em geometric degree of the equation system}. Replacing the notion of geometric degree of the given polynomial equation system by a suitably defined {\em real (or complex) degree} of certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.4.2. <s> Let \(S_0\) be a smooth and compact real variety given by a reduced regular sequence of polynomials \(f_1, \ldots, f_p\). This paper is devoted to the algorithmic problem of finding efficiently a representative point for each connected component of \(S_0\) . For this purpose we exhibit explicit polynomial equations that describe the generic polar varieties of \(S_0\). This leads to a procedure which solves our algorithmic problem in time that is polynomial in the (extrinsic) description length of the input equations \(f_1,\ldots, f_p\) and in a suitably introduced, intrinsic geometric parameter, called the degree of the real interpretation of the given equation system \(f_1,\ldots,f_p\). <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.4.2. <s> Let f 1 , ldots, f s be polynomials in Q[X 1 , ..., X n ] that generate a radical ideal and let V be their complex zero-set. Suppose that V is smooth and equidimensional; then we show that computing suitable sections of the polar varieties associated to generic projections of V gives at least one point in each connected component of V ∩ Rn. We deduce an algorithm that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations. Its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity. <s> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.4.2. <s> Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets. <s> BIB004 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.4.2. <s> Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algebraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article we propose a new algorithm for the former task, which avoids a hypothesis of properness required in many of the previous methods. We show how studying the set of non-properness of a linear projection ź enables us to detect the connected components of a real algebraic set without critical points for ź. Our algorithm is based on this observation and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples. <s> BIB005 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 2.4.2. <s> We present a new probabilistic algorithm to find a finite set of points intersecting the closure of each connected component of the realization of every sign condition over a family of real polynomials defining regular hypersurfaces that intersect transversally. This enables us to show a probabilistic procedure to list all feasible sign conditions over the polynomials. In addition, we extend these results to the case of closed sign conditions over an arbitrary family of real multivariate polynomials. The complexity bounds for these procedures improve the known ones. <s> BIB006
Quantifier Elimination Algorithm. The above ingredients (namely, the Block Elimination Algorithm and the Sign Determination Algorithm), along with numerous technical detail which we omit in this survey, allows one to prove the following result. Theorem 2.18. [17] Let P be a set of at most s polynomials each of degree at most d in k + variables with coefficients in a real closed field R, and let Π denote a partition of the list of variables (X 1 , . . . , X k ) into blocks, X BIB001 , . . . , X [ω] , where the block , a (P, Π)-formula, there exists an equivalent quantifier free formula, where P ijn (Y ) are polynomials in the variables Y , σ ijn ∈ {0, 1, −1}, and the degrees of the polynomials P ijk (y) are bounded by d O(kω)···O(k1) . Moreover, there is an algorithm to compute Ψ(Y ) with complexity Remark 2.19. The algorithmic results described in Section 2.2 are based on one common technique -namely, by taking a well chosen infinitesimal perturbation, one can replace any bounded, real (possibly singular) variety V ⊂ R k , by a non-singular variety defined over an (non-archimedean) extension of R, and the projection map on some co-cordinate (say X 1 ) restricted to this variety has non-degenerate critical points, which moreover are defined by a zero-dimensional system of equations which is nicely behaved (is automatically a Gröbner basis). The limits of these critical points belong to the given variety V and moreover they meet every semialgebraically connected component of V . This technique (which is rather special to real algebraic geometry as opposed to complex geometry) has several advantages from the point of view of algorithmic complexity. The first advantage is that it is not necessary to choose any generic co-ordinate system or direction to project on. Secondly, the method does not care about how singular the given variety V is or even its dimension. Moreover, it is possible to relate the topology (up to semialgebraic homotopy equivalence) of V with the infinitesimal "tube" around it which is bounded by the perturbed hyper-surface (say V ). This reduces most algorithmic problems of computing topological invariants of V , to that of the well-behaved hyper-surface V . Since the degree of the polynomial defining V is at most twice that of the one defining V , and the computations take place in the original ring adjoined with at most a constant many (i.e. their number is independent of the input parameters s, d and k) infinitesimals, the complexity is well controlled. The main disadvantage of the approach (which could a drawback from the point of view of practical implementation point) is that computations with even a constant many infinitesimals are quite expensive (even though they do not affect the asymptotic complexity bounds). Also, the process of taking algebraic limits at the end can be quite cumbersome. Nevertheless, this perturbation approach remains the only one which gives deterministic algorithms with the best known worst case complexity estimates. 2.5. Intrinsic complexity and complex algebraic techniques. The model for studying complexity of algorithms in this survey is that the size of the input is measured in terms of the number of coefficients needed to specify the input polynomials in the dense representation. Since this number is determined by the following parameters: (1) the number of variables, k; (2) the number of polynomials, s; (3) the degrees of the polynomials, d; it makes sense to state the complexity estimates in terms of s, d and k. There is another body of work (see for example BIB001 BIB002 BIB003 BIB005 BIB006 ) in which the goal is to obtain algorithms for computing sample points on each semi-algebraically connected component of a given real algebraic variety V ⊂ R k , whose complexity is bounded by a polynomial function of some intrinsic invariant of the variety V or in some cases the length of straight line programs encoding the input polynomials. In this approach, the real variety V is considered as the real part of the complex variety V C ⊂ C k (where C is the algebraic closure of R), and the intrinsic invariant, δ(V ) = δ(V C ) depends only on the geometry of the complex variety V C , and not on the particular presentation of it by the given input polynomials. If d is a bound on the degrees of the polynomials defining V , then δ(V ) is bounded by O(d) k and could be as large as d k in the worst case. However, δ(V ) could be smaller in special cases. Since these algorithms aim at complexity in terms of some geometric invariant of the variety itself, the infinitesimal perturbation techniques described in the previous sections is not available, since such a perturbation will not in general preserve this invariant. Hence, one needs to work directly with the given variety. For example, one needs to prove that under certain assumptions on the variety, the critical points of a generic projection (also called the polar variety) is non-singular (see  ). The theory of geometric resolutions (see BIB002 ) play an important role in these algorithms. One feature of the algorithms that follow from these techniques is that it is necessary to choose generic co-ordinates which cannot be done deterministically within the claimed complexity bounds. As such one obtains probabilistic (as opposed to deterministic) algorithms, meaning that these algorithms always run within the stated complexity time bounds, but is guaranteed to give correct results only with high probability. 2.6. Variants of quantifier elimination and applications. In certain applications (most notably in the theory of constraint databases) one needs to perform quantifier elimination in a more generalized setting than that discussed above. For instance, it is sometimes necessary to eliminate quantifiers not just from one formula, but a whole sequence of formulas described in some finite terms, where the number of free variables is allowed to grow in the sequence. Clearly, the quantifier elimination algorithms described previously is not sufficient for this purpose since their complexity depends on the number of free variables. We describe below a variant of the quantifier elimination problem which was introduced in  motivated by a problem in constraint databases. 2.6.1. The Uniform Quantifier Elimination Problem. Definition 2.20. We call a sequence, of first-order formulas φ n in the language of ordered fields, to be a uniform sequence if each φ n has the form, where Q i ∈ {∨, ∧}, 1 ≤ i ≤ ω and φ is some fixed ( + ω)-ary quantifier-free firstorder formula. Thus for every n, φ n is a first order formula with + n free variables. We will refer to the variables T 1 , . . . , T as parameters. Given a uniform sequence of formulas Φ = {φ n | n > 0}, where . . , Y kω ), we define the size of Φ to be the length of the formula φ. Example 2.21. Consider the uniform sequence of formulas Consider the sequence of quantified formulas, (∃T 1 )φ n (T 1 , Y 1 , . . . , Y n ). In this example, it is easily seen that letting we get a uniform sequence of quantifier-free formulas satisfying, The uniform quantifier elimination problem is to eliminate quantifiers from a uniform sequence of formulas and obtain another uniform sequence of quantifier free formulas. The following is proved in  . be a uniform sequence of formulas with parameters T 1 , . . . , T , where Let R 1 , . . . , R m ∈ {∃, ∀}, R i = R i+1 , and let T BIB001 , . . . , T [m] be a partition of the variables, T 1 , . . . , T into m blocks of size 1 , . . . , m , where 1≤i≤m i = . Then, there exists an algorithm that outputs a quantifier-free first order formula, The complexity of the algorithm is bounded by and the size of the formula ψ is bounded by Remark 2.23. In [6] Theorem 2.22 is used to prove the equivalence of two different semantics and in the theory of constraint databases. However, it also has applications in logic. For example, in the same paper it is used to prove that semi-algebraic connectivity is not expressible by a first-order formula (see  for a precise definition of first-order expressibility). This inexpressibility result has as a consequence that we cannot hope to use quantifier-elimination directly to check whether a given semi-algebraic set is semi-algebraically connected (unlike other first-order expressible topological properties such as being open or closed etc. where it is possible to do so). Note that the inexpressibility result was also proved by more abstract model theoretic methods in  . The technique used in the proof of Theorem 2.22 is also used in  to give an algorithm for ordinary quantifier elimination whose complexity depends on the size of the input formula, and which has better complexity than the algorithm in Theorem 2.18 in case the input formula has a small size. This algorithm is called Local Quantifier Elimination Algorithm in BIB004 .