We prove that the depth of any arithmetic network for deciding membership in a semialgebraic set \({\Sigma \subset \mathbb{R}^{n}}\) is bounded from below by #R##N##R##N#$$c_1 \sqrt{ \frac{\log ({\rm b}(\Sigma))}{n}} -c_2 \log n,$$#R##N##R##N#where \({{\rm b}(\Sigma)}\) is the sum of the Betti numbers of \({\Sigma}\) with respect to “ordinary” (singular) homology, and c1, c2 are some (absolute) positive constants. This result complements the similar lower bound in Montana et al. (Appl Algebra Engrg Comm Comput 7:41–51, 1996) for locally closed semialgebraic sets in terms of the sum of Borel–Moore Betti numbers.
['Andrei Gabrielov', 'Nicolai Vorobjov']
Topological lower bounds for arithmetic networks