On Topological Lower Bounds for Algebraic Computation Trees

详细信息    查看全文

• 作者：Andrei Gabrielov ; Nicolai Vorobjov
• 关键词：Complexity lower bounds ; Algebraic computation trees ; Semialgebraic sets
• 刊名：Foundations of Computational Mathematics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：17
• 期：1
• 页码：61-72
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Numerical Analysis; Economics, general; Applications of Mathematics; Linear and Multilinear Algebras, Matrix Theory; Math Applications in Computer Science; Computer Science, general;
• 出版者：Springer US
• ISSN：1615-3383
• 卷排序：17

文摘

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.KeywordsComplexity lower boundsAlgebraic computation treesSemialgebraic setsCommunicated by Felipe Cucker.