ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.6.3. <s> This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.6.3. <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> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.6.3. <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> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.6.3. <s> For any $\ell>0$, we present an algorithm which takes as input a semi-algebraic set, $S$, defined by $P_1 \leq 0,...,P_s \leq 0$, where each $P_i \in \R[X_1,...,X_k]$ has degree $\leq 2,$ and computes the top $\ell$ Betti numbers of $S$, $b_{k-1}(S), ..., b_{k-\ell}(S),$ in polynomial time. The complexity of the algorithm, stated more precisely, is $ \sum_{i=0}^{\ell+2} {s \choose i} k^{2^{O(\min(\ell,s))}}. $ For fixed $\ell$, the complexity of the algorithm can be expressed as $s^{\ell+2} k^{2^{O(\ell)}},$ which is polynomial in the input parameters $s$ and $k$. To our knowledge this is the first polynomial time algorithm for computing non-trivial topological invariants of semi-algebraic sets in $\R^k$ defined by polynomial inequalities, where the number of inequalities is not fixed and the polynomials are allowed to have degree greater than one. For fixed $s$, we obtain by letting $\ell = k$, an algorithm for computing all the Betti numbers of $S$ whose complexity is $k^{2^{O(s)}}$. <s> BIB004 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.6.3. <s> Let $\R$ be a real closed field, $ {\mathcal Q} \subset \R[Y_1,...,Y_\ell,X_1,...,X_k], $ with $ \deg_{Y}(Q) \leq 2, \deg_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m,$ and $ {\mathcal P} \subset \R[X_1,...,X_k] $ with $\deg_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$, and $S \subset \R^{\ell+k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0, P \geq 0, P \leq 0, P \in {\mathcal P} \cup {\mathcal Q}$. We prove that the sum of the Betti numbers of $S$ is bounded by \[ \ell^2 (O(s+\ell+m)\ell d)^{k+2m}. \] This is a common generalization of previous results on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree $d$ and 2, respectively. ::: We also describe an algorithm for computing the Euler-Poincar\'e characteristic of such sets, generalizing similar algorithms known before. The complexity of the algorithm is bounded by $(\ell s m d)^{O(m(m+k))}$. <s> BIB005 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.6.3. <s> Let $\R$ be a real closed field, $ {\mathcal Q} \subset \R[Y_1,...,Y_\ell,X_1,...,X_k], $ with $ °_{Y}(Q) \leq 2, °_{X}(Q) \leq d, Q \in {\mathcal Q}, #({\mathcal Q})=m,$ and $ {\mathcal P} \subset \R[X_1,...,X_k] $ with $°_{X}(P) \leq d, P \in {\mathcal P}, #({\mathcal P})=s$, and $S \subset \R^{\ell+k}$ a semi-algebraic set defined by a Boolean formula without negations, with atoms $P=0, P \geq 0, P \leq 0, P \in {\mathcal P} \cup {\mathcal Q}$. We prove that the sum of the Betti numbers of $S$ is bounded by $(\ell s m d)^{O(m+k)}$. This is a common generalization of previous results known before on bounding the Betti numbers of closed semi-algebraic sets defined by polynomials of degree $d$ and 2, respectively. ::: We also describe algorithms for computing the Euler-Poincare characteristic, as well as all the Betti numbers of such sets. The complexity of the first algorithm is bounded by $(\ell s m d)^{O(m(m+k))}$, while that of the second is bounded by $(\ell s m d)^{2^{O(m+k)}}$. <s> BIB006
Significance from the computational complexity theory viewpoint. Semi-algebraic sets defined by a system of quadratic inequalities have a special significance in the theory of computational complexity. Even though such sets might seem to be the next simplest class of semi-algebraic sets after sets defined by linear inequalities, from the point of view of computational complexity they represent a quantum leap. Whereas there exist (weakly) polynomial time algorithms for solving linear programming, solving quadratic feasibility problem is provably hard. For instance, it follows from an easy reduction from the problem of testing feasibility of a real quartic equation in many variables, that the problem of testing whether a system of quadratic inequalities is feasible is NP R -complete in the Blum-Shub-Smale model of computation (see BIB002 ). Assuming the input polynomials to have integer coefficients, the same problem is NP-hard in the classical Turing machine model, since it is also not difficult to see that the Boolean satisfiability problem can be posed as the problem of deciding whether a certain semi-algebraic set defined by quadratic inequalities is empty or not. Counting the number of semi-algebraically connected components of such sets is even harder. In fact, it is PSPACE-hard BIB001 (PSPACE is a complexity class which contains the entire polynomial hierarchy), and the proof of this results extend easily to the quadratic case. Moreover, it is proved in BIB004 for = O(log k), computing the -th Betti number of a basic semialgebraic set defined by quadratic inequalities in R k is PSPACE-hard. In view of these hardness results, it is unlikely that there exist polynomial time algorithms for computing the Betti numbers (or even the first few Betti numbers) of such a set. From this point of view, Theorem 3.30 is quite surprising, since it gives a polynomial time algorithm for computing certain Betti numbers of a class of semi-algebraic sets for which computing the zero-th Betti number is already PSPACE-hard. 3.6.4. Semi-algebraic sets defined by partially quadratic systems. We have discussed topological as well as algorithmic results concerning general semi-algebraic sets, as well as those defined by quadratic constraints In BIB005 , the authors try to interpolate between results known for general semi-algebraic sets (defined by polynomials of arbitrary degrees) and those known for semi-algebraic sets defined by polynomials of degree at most 2. In order to do so they consider semi-algebraic sets defined by polynomial inequalities, in which the dependence of the polynomials on a subset of the variables is at most quadratic. As a result we obtain common generalizations of the bounds stated in Theorems 3.2 and 3.25. Given any polynomial P ∈ R[X 1 , . . . , X k , Y 1 , . . . , Y ], we will denote by deg X (P ) (resp. deg Y (P )) the total degree of P with respect to the variables X 1 , . . . , X k (resp. Y 1 , . . . , Y ). Denote by , a family of polynomials with The following theorem that interpolates between Theorems 3.1 and 3.25 above is proved in BIB005 . In particular, for m ≤ , we have Notice that Theorem 3.31 can be seen as a common generalization of Theorems 3.2 and 3.25, in the sense that we recover similar bounds (that is bounds having the same shape) as in Theorem 3.2 (respectively Theorem 3.25) by setting and m (respectively s, d and k) to O(1). Note also that as a special case of Theorem 3.31 we obtain a bound on the sum of the Betti numbers of a semi-algebraic set defined over a quadratic map. As mentioned before, such sets have been considered from an algorithmic point of view in BIB003 , where an efficient algorithm is described for computing sample points in every semi-algebraically connected component, as well as testing emptiness, of such sets. More precisely we have: The techniques developed in this paper for obtaining tight bounds on the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials also pave the way towards designing more efficient algorithms for computing the Euler-Poincaré characteristic as well as the Betti numbers of such sets. The following theorem appears in BIB005 . Theorem 3.33. There exists an algorithm that takes as input the description of a (P ∪ Q)-closed semi-algebraic set S (following the same notation as in Theorem 3.31) and outputs its the Euler-Poincaré characteristic χ(S). The complexity of this algorithm is bounded by ( smd) O(m(m+k)) . In the case when S is a basic closed semi-algebraic set the complexity of the algorithm is ( smd) O(m+k) . The algorithm for computing all the Betti numbers has complexity ( smd) and its description can be found in BIB006 . While the complexity of both the algorithms discussed above is polynomial for fixed m and k, the complexity of the algorithm for computing the Euler-Poincaré characteristic is significantly better than that of the algorithm for computing all the Betti numbers. Note that the first versions of both these algorithms for computing the EulerPoincaré characteristic as well as the Betti numbers of semi-algebraic sets defined by purely quadratic constraints having complexity which is polynomial for fixed number of constraints, appeared first in  and BIB004 respectively. The extensions of these algorithms to semi-algebraic sets defined by partially quadratic systems were made in BIB005 and BIB006 respectively. These latter results indicate that the problem of computing the Betti numbers of semi-algebraic sets defined by a constant number of polynomial inequalities is solvable in polynomial time, even if we allow a small (constant sized) subset of the variables to occur with degrees larger than two in the polynomials defining the given set.