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.