ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> More Efficient Algorithms for Computing the Number of Connected Components for General Semi-algebraic Sets ? <s> Let $M\subset \mathbb{R}^n$ be a connected component of an algebraic set $\varphi^{-1}(0)$ , where $\varphi$ is a polynomial of degree $d$ . Assume that $M$ is contained in a ball of radius $r$ . We prove that the geodesic diameter of $M$ is bounded by $2r\nu(n)d(4d-5)^{n-2}$ , where $\nu(n)=2{\Gamma({1}/{2})\Gamma(({n+1})/{2})}{\Gamma({n}/{2})}^{-1}$ . This estimate is based on the bound $r\nu(n)d(4d-5)^{n-2}$ for the length of the gradient trajectories of a linear projection restricted to $M$ . <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> More Efficient Algorithms for Computing the Number of Connected Components for General Semi-algebraic Sets ? <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> BIB002
A very interesting open question is whether the exponent O(k 2 ) in the complexity of roadmap algorithms (cf. Theorem 3.6) can be improved to O(k), so that the complexity of testing connectivity becomes asymptotically the same as that of testing emptiness of a semi-algebraic set (cf. Theorem 2.15). Recent improvements in the complexity of roadmap algorithms described in Section 3.1.2 above, certainly gives some hope in this regard. Such an improvement would go a long way in making this algorithm practically useful. It would also be of interest for studying metric properties of semi-algebraic sets because of the following. Applying Crofton's formula from integral geometry one immediately obtains as a corollary of Theorem 3.6 (using the same notation as in the theorem) an upper bound of on the length of a semi-algebraic connecting path connecting two points in any semi-algebraically connected component of S (assuming that S is contained in the unit ball centered at the origin). An improvement in the complexity of algorithms for constructing connecting paths (such as the roadmap algorithm) would also improve the bound on the length of connecting paths. Recent results due to D'Acunto and Kurdyka BIB001 show that it is possible to construct semi-algebraic paths of length d O(k) between two points of S (assuming that S is a semi-algebraically connected component of a real algebraic set contained in the unit ball defined by polynomials of degree d). However, the semi-algebraic complexity of such paths cannot be bounded in terms of the parameters d and k. The improvement in the complexity suggested above, apart from its algorithmic significance, would also be an effective version of the results in BIB001 . Remove the compactness assumption in Theorem 3.22. More generally, investigate the role of compactness in the Blum-Shub-Smale model of computations over real closed fields (see BIB002 for more details).