ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.4. <s> In this paper, two interesting complexity classes, PP and $ \oplus {\text{P}}$, are compared with PH, the polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turing reducible to a set in PP, and PH is included in ${\text{BP}} \cdot \oplus {\text{P}}$. As a consequence of the results, it follows that ${\text{PP}} \subseteq {\text{PH}}$ (or $\oplus {\text{P}} \subseteq {\text{PH}}$) implies a collapse of PH. A stronger result is also shown: every set in PP(PH) is polynomial-time Turing reducible to a set in PP. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.4. <s> We consider the problem of deciding whether a given system of quadratic homogeneous equations over the reals has non-trivial solution. We design an approximative algorithm whose complexity is polynomial in the number of variables and exponential in the number of equations. Some applications to general systems of polynomial equations and inequalities over the reals are discussed. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.4. <s> 1 Introduction.- 2 Definitions and First Properties of Computation.- 3 Computation over a Ring.- 4 Decision Problems and Complexity over a Ring.- 5 The Class NP and NP-Complete Problems.- 6 Integer Machines.- 7 Algebraic Settings for the Problem "P ? NP?".- 8 Newton's Method.- 9 Fundamental Theorem of Algebra: Complexity Aspects.- 10 Bezout's Theorem.- 11 Condition Numbers and the Loss of Precision of Linear Equations.- 12 The Condition Number for Nonlinear Problems.- 13 The Condition Number in ?(H(d).- 14 Complexity and the Condition Number.- 15 Linear Programming.- 16 Deterministic Lower Bounds.- 17 Probabilistic Machines.- 18 Parallel Computations.- 19 Some Separations of Complexity Classes.- 20 Weak Machines.- 21 Additive Machines.- 22 Nonuniform Complexity Classes.- 23 Descriptive Complexity.- References. <s> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.4. <s> This paper investigates the complexity of stratification computation for semialgebraic sets. An upper bound for the computation of canonical stratifications is given for a wide class of stratifying conditions called here admissible. For such conditions, the stratifying process is at most doubly exponential in the depth of the stratification. Usual conditions of regularity like Whitney conditions (a) and (b) or Bekka condition (C) are admissible. A useful criterion and tools are given in order to prove easily other admissibilities. <s> BIB004 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.4. <s> A classic result in real algebraic geometry due to Oleinik-Petrovsky, Thom and Milnor, bounds the {\em topological complexity} (the sum of the Betti numbers) of basic semi-algebraic sets. This bound is tight as one can construct examples having that many connected components. However, till now no significantly better bounds were known on the individual higher Betti numbers. In this paper we prove separate bounds on the different Betti numbers of basic semi-algebraic sets, as well as arrangements of algebraic hypersurfaces. These are the first results in this direction. <s> BIB005 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.4. <s> Given a quadratic map $$Q:\mathbb{K}^n \to \mathbb{K}^k $$ defined over a computable subring D of a real closed field $$\mathbb{K},$$ and p ?D[Y1,...,Yk] of degree d, we consider the zero set $$Z = Z(p(Q(X)), \mathbb{K}^n) \subseteq \mathbb{K}^n$$ of p(Q(X1,...,Xn)) ?D[X1,...,Xn]. We present a procedure that computes, in (dn)O(k) arithmetic operations in D, a set $$\mathcal{S}$$ of (real univariate representations of) sampling points in $$\mathbb{K}^n$$ that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the known methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure is only capable of deciding in $$n^{O(k^2 )} $$ operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=?iYi2 and homogeneous Q. ::: ::: A by-product of our procedure is a bound (dn)O(k) on the number of connected components of Z. ::: ::: The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending $$\mathbb{K}$$ by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets. <s> BIB006 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.4. <s> Toda proved in 1989 that the (discrete) polynomial time hierarchy, $\mathbf{PH}$, is contained in the class $\mathbf{P}^{#\mathbf{P}}$, namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class $#\mathbf{P}$. This result which illustrates the power of counting is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum-Shub-Smale real machines) has been missing so far. In this paper we formulate and prove a real analogue of Toda's theorem. Unlike Toda's proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry -- namely the problem of deciding sentences in the first order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result might be of independent interest to researchers in algorithmic semi-algebraic geometry. <s> BIB007
Relation between the complexity of quantifier elimination and the complexity of computing Betti numbers. It is clear from the previous sections that there are two important strands of research in algorithms in real algebraic geometry, namely (1) Algorithms for deciding sentences in the first-order theory of the reals (with several blocks of quantifiers); (2) Computing topological invariants of semi-algebraic sets (such as their Betti numbers). While these two classes of problems might seem quite different, the following reduction result gives a polynomial time reduction of the problem of deciding quantified sentences in the first order theory of the reals with a fixed number of quantifiers to the problem of computing Betti numbers of semi-algebraic sets. For technical reasons, the reduction is only proved for a certain sub-class of formulas which is defined more precisely below.  where for each i, ) is a block of k i +1 variables, Q i ∈ {∃, ∀}, with Q j = Q j+1 , 1 ≤ j < ω, and φ is a quantifier-free formula defining a closed semi-algebraic subset S of S k1 × · · · × S kω . Output. True or False depending on whether Φ is true or false in the first order theory of R. Notation 4. For any semi-algebraic set S ⊂ R k , we denote by P S (T ), denote the Poincaré polynomial of S -namely, Input. A quantifier-free formula defining a semi-algebraic set S ⊂ R k . Output. The Poincaré polynomial P S (T ). The following reduction result appears in BIB007 . It says that with a mild hypothesis of compactness, the General Decision Problem with a fixed number of quantifier alternations can be reduced in polynomial time to the problem of computing Betti numbers of semi-algebraic sets. Theorem 3.22. [25] For every ω > 0, there is a deterministic polynomial time reduction of GDP c ω to Poincaré. Remark 3.23. Theorem 3.22 is motivated by a well known theorem due to Toda BIB001 in discrete complexity theory which relates two complexity classes -namely the polynomial hierarchy and the complexity class #P. Theorem 3.22 can be viewed as an analogue of Toda's theorem in the Blum-Shub-Smale model of computations over arbitrary real closed fields BIB003 (see also BIB007 ). The main ingredients in the proof of Theorem 3.22 is an efficient semi-algebraic realization of the iterated fibered join of a semi-algebraic set with itself over a semi-algebraic map, and Alexander duality that allows one to express the Poincaré polynomial of a semi-algebraic subset of the sphere in terms of its complement in the sphere. 3.5. Effective semi-algebraic triangulation and stratification. As mentioned above in Section 2.1.2 one obtains an algorithm for computing a semi-algebraic triangulation of semi-algebraic sets using cylindrical algebraic decomposition (after making a generic linear change of co-ordinates). The complexity of this is algorithm dominated by the cost of the performing the cylindrical algebraic decomposition, and is thus doubly exponential. Algorithms for computing stratifications of semi-algebraic sets, such that the strata satisfy additional regularity conditions (such as Whitney conditions (a) and (b)) have been considered by several authors. Rannou BIB004 gave an algorithm for obtaining stratification with regularity conditions that imply the Whitney conditions. The complexity of this algorithm is doubly exponential in the depth of the stratification. Finding a singly exponential algorithm for computing stratifications of semi-algebraic sets remains a major open problem (see Section 5). 3.6. Semi-algebraic sets defined by quadratic and partially quadratic systems. A restricted class of semi-algebraic sets -namely, semi-algebraic sets defined by quadratic inequalities -has been considered by several researchers BIB002  BIB006 . As in the case of general semi-algebraic sets, the Betti numbers of such sets can be exponentially large in the number of variables, as can be seen in the following example. Example 3.24. The set S ⊂ R defined by However, it turns out that for a semi-algebraic set S ⊂ R defined by m quadratic inequalities, it is possible to obtain upper bounds on the Betti numbers of S which are polynomial in and exponential only in m. The first such result is due to Barvinok [5] , who proved the following theorem. Remark 3.26. Notice that the bound in Theorem 3.25 is polynomial in the dimension for fixed m, and this fact depends crucially on the assumption that the degrees of the polynomials Q 1 , . . . , Q m are at most two. For instance, the semi-algebraic set defined by a single polynomial of degree 4 can have Betti numbers exponentially large in , as exhibited by the semi-algebraic subset of R defined by The above example illustrates the delicate nature of the bound in Theorem 3.25, since a single inequality of degree 4 is enough to destroy the polynomial nature of the bound. In contrast to this, it is shown in Theorem 3.31 below that a polynomial bound on the Betti numbers of S continues to hold, even if we allow a few (meaning any constant number) of the variables to occur with degrees larger than two in the polynomials used to describe the set S. The bound on the sum of all the Betti numbers in Theorem 3.25 has exponential dependence on the number of inequalities. This dependence is unavoidable, since the semi-algebraic set S ⊂ R k defined by has b 0 (S) = 2 k . Hence, it is somewhat surprising that for any fixed constant , the Betti numbers b k−1 (S), . . . , b k− (S), of a basic closed semi-algebraic set S ⊂ R k defined by quadratic inequalities, are polynomially bounded. The following theorem appears in BIB005 . Theorem 3.27. Let R a real closed field and S ⊂ R k be defined by Then, for ≥ 0, 3.6.1. Algorithm for testing emptiness. The problem of deciding whether a given semi-algebraic set defined by a finite set of quadratic inequalities is empty or not was considered first by Barvinok BIB002 who proved the following theorem.