On Topological Lower Bounds for Algebraic Computation Trees

We prove that the height of any algebraic computation tree for deciding membership in a semialgebraic set \(\Sigma \subset {\mathbb R}^n\) is bounded from below by

$$\begin{aligned} \frac{c_1\log (\mathrm{b}_m(\Sigma ))}{m+1} -c_2n, \end{aligned}$$

where \(\mathrm{b}_m(\Sigma )\) is the mth Betti number of \(\Sigma \) with respect to “ordinary” (singular) homology and \(c_1,\ c_2\) are some (absolute) positive constants. This result complements the well-known lower bound by Yao (J Comput Syst Sci 55:36–43, 1997) for locally closed semialgebraic sets in terms of the total Borel–Moore Betti number. We also prove that if \(\rho :\> {\mathbb R}^n \rightarrow {\mathbb R}^{n-r}\) is the projection map, then the height of any tree deciding membership in \(\Sigma \) is bounded from below by

$$\begin{aligned} \frac{c_1\log (\mathrm{b}_m(\rho (\Sigma )))}{(m+1)^2} -\frac{c_2n}{m+1} \end{aligned}$$

for some positive constants \(c_1,\ c_2\). We illustrate these general results by examples of lower complexity bounds for some specific computational problems.