ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.3. <s> A tamper-evident top closure lid construction for a container. The lid is integrally formed from a plastic cover member, the member carrying a main and a secondary paperboard insert on its upper surface, the member and insert being bonded together. The plastic cover member has an integral tongue to define, upon tongue pivoting, an opening in the member. The main paperboard insert is hinged about a contiguous pivot axis. The secondary insert carries a pull tab. If formed from a brittle plastics material, pulling the pull tab breaks the plastics member at its tongue hinge. The pull tab is so formed as to indicate tampering to a prospective purchaser of the container provided with the top closure lid construction of this invention. The lid may also be provided with an upstanding rim to facilitate stacking. <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.3. <s> Abstract. In this paper we prove new bounds on the sum of the Betti numbers of closed semi-algebraic sets and also give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. Given a closed semi-algebraic set S ::: $\subset$ Rk defined as the intersection of a real variety, Q=0, deg(Q)≤d, whose real dimension is k', with a set defined by a quantifier-free Boolean formula with no negations with atoms of the form Pi=0, Pi≥ 0, Pi≤ 0, deg(Pi) ≤ d, 1≤ i≤ s, we prove that the sum of the Betti numbers of S is bounded by sk'(O(d))k . This result generalizes the Oleinik—Petrovsky—Thom—Milnor bound in two directions. Firstly, our bound applies to arbitrary unions of basic closed semi-algebraic sets, not just for basic semi-algebraic sets. Secondly, the combinatorial part (the part depending on s ) in our bound, depends on the dimension of the variety rather than that of the ambient space. It also generalizes the result in [4] where a similar bound is proven for the number of connected components. We also prove that the sum of the Betti numbers of S is bounded by sk' 2O(k2 m4) in case the total number of monomials occurring in the polynomials in ::: $ {\cal P} \cup \{Q\}$ is m. Using the tools developed for the above results, as well as some additional techniques, we give the first single exponential time algorithm for computing the Euler characteristic of arbitrary closed semi-algebraic sets. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 3.3. <s> Computing various topological invariants of semi-algebraic sets in single exponential time is an active area of research. Several algorithms are known for deciding emptiness, computing the number of connected components of semi-algebraic sets in single exponential time etc. However, an algorithm for computing all the Betti numbers of a given semi-algebraic set in single exponential time is still lacking. In this paper we describe a new, improved algorithm for computing the Euler--Poincare characteristic (which is the alternating sum of the Betti numbers) of the realization of each realizable sign condition of a family of polynomials restricted to a real variety. The complexity of the algorithm is $$s^{k'+1}O(d)^{k} + s^{k'}((k' log_{2}(s) + k log_{2}(d))d)^{O(k)},$$ where s is the number of polynomials, k the number of variables, d a bound on the degrees, and k0 the real dimension of the variety. A consequence of our result is that the Euler--Poincare characteristic of any locally closed semi-algebraic set can be computed with the same complexity. The best previously known single exponential time algorithm for computing the Euler--Poincare characteristic of semi-algebraic sets worked only for a more restricted class of closed semi-algebraic sets and had a complexity of (ksd)O(k). <s> BIB003
Computing generalized Euler-Poincaré characteristic. As mentioned before in Section 2.4.1, efficient algorithms for sign determination of univariate polynomials described in BIB001  are amongst the most basic algorithms in algorithmic real algebraic geometry. Given P ⊂ R[X], Q ∈ R[X] with card P = s, and deg(P ) ≤ d for P ∈ P ∪ {Q}, these algorithms count for each realizable sign condition of the family P, the cardinality of the set of real zeros of Q, lying in the realization of that sign condition. The complexity of the algorithm in  is sd O(1) . In the multidimensional case, it is no longer meaningful to talk about the cardinalities of the zero set of Q lying in the realizations of different sign conditions of P. However, there exists another discrete valuation on semi-algebraic sets that properly generalizes the notion of cardinality. This valuation is the Euler-Poincaré characteristic. The Euler-Poincaré characteristic, χ(S), of a closed and bounded semialgebraic set S ⊂ R k is defined as where b i (S) is the rank of the i-th simplicial homology group of S. Note that with this definition, χ(∅) = 0, and χ(S) = card S, whenever card S < ∞. Moreover, χ is additive. The Euler-Poincaré characteristic defined above for closed and bounded semialgebraic set can be extended additively to all semi-algebraic sets. This generalized Euler-Poincaré characteristic is then a homeomorphism (but not a homotopy) invariant, and establishes an isomorphism between the Grothendieck ring, K 0 (sa), of homeomorphism classes of semi-algebraic sets and Z. The problem of determining the Euler-Poincaré characteristic of P-closed semialgebraic sets was considered in BIB002 where an algorithm was presented for computing the Euler-Poincaré characteristic of a given P-closed semi-algebraic set. The complexity of the algorithm is (ksd) O(k) . Moreover, in the special case when the coefficients of the polynomials in P are integers of bit lengths bounded by τ , the algorithm performs at most (ksd) The following result (which should be viewed as a generalization of the univariate sign determination algorithm) appears in BIB003 . Theorem 3.19. There exists an algorithm which given an algebraic set Z = Z(Q, R k ) ⊂ R k and a finite set of polynomials P = {P 1 , . . . , P s } ⊂ R[X 1 , . . . , X k ], computes the list χ(P, Z) indexed by elements, σ, of Sign(P, Z). If the degrees of the polynomials in P ∪ {Q} are bounded by d, and the real dimension of Z = Z(Q, R k ) is k , then the complexity of the algorithm is If the coefficients of the polynomials in P ∪ {Q} are integers of bit-sizes bounded by τ , then the bit-sizes of the integers appearing in the intermediate computations and the output are bounded by τ ((k log 2 (s)