On topological lower bounds for algebraic computation trees

DOI10.1007/S10208-015-9283-7MaRDI QIDQ525599zbMATH OpenOpenAlexFDO

Authors Andrei Gabrielov, Nicolai Vorobjov

Publication date 5 May 2017

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.04341

zbMATH Keywords

semialgebraic setsalgebraic computation treescomplexity lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Topology of real algebraic varieties (14P25) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: We prove that the height of any algebraic computation tree for deciding membership in a semialgebraic set is bounded from below (up to a multiplicative constant) by the logarithm of m-th Betti number (with respect to singular homology) of the set, divided by m+1. This result complements the well known lower bound by Yao for locally closed semialgebraic sets in terms of the total Borel-Moore Betti number. We also prove that the height is bounded from below by the logarithm of m-th Betti number of a projection of the set onto a coordinate subspace, divided by (m+1)^2. We illustrate these general results by examples of lower complexity bounds for some specific computational problems.

Recommendations

• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Complexity lower bounds for approximation algebraic computation trees
• Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs
• scientific article; zbMATH DE number 528937
• Topological lower bounds on algebraic random access machines
• Lower bounds in algebraic computational complexity
• scientific article; zbMATH DE number 1500505
• Tree-width in algebraic complexity
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• scientific article; zbMATH DE number 503392

Cites work

• scientific article; zbMATH DE number 2196510 (Why is no real title available?)
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• Decision tree complexity and Betti numbers
• On the complexity of computations under varying sets of primitives

Cited in

(10)

• Lower bounds for the non-linear complexity of algebraic computation trees with integer inputs
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Time and space complexity of deterministic and nondeterministic decision trees
• Decision tree complexity and Betti numbers
• Topological perplexity of feedback stabilization
• scientific article; zbMATH DE number 4047106 (Why is no real title available?)
• Lifting lower bounds for tree-like proofs
• Rough analysis of computation trees
• Topological lower bounds for arithmetic networks
• scientific article; zbMATH DE number 1984321 (Why is no real title available?)

This page was built for publication: On topological lower bounds for algebraic computation trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q525599)