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_1log (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_1log (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.