On topological lower bounds for algebraic computation trees

DOI10.1007/S10208-015-9283-7zbMATH Open1365.14080arXiv1502.04341OpenAlexW2963960422MaRDI QIDQ525599FDOQ525599

Nicolai Vorobjov, Andrei Gabrielov

Publication date: 5 May 2017

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

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.

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

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

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)

Cites Work

• BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• Decision tree complexity and Betti numbers
• Title not available (Why is that?)
• Betti numbers of semialgebraic sets defined by quantifier-free formulae
• On the complexity of computations under varying sets of primitives

Cited In (9)

• 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
• Topological perplexity of feedback stabilization
• Title not available (Why is that?)
• Lifting lower bounds for tree-like proofs
• Rough analysis of computation trees
• Topological lower bounds for arithmetic networks
• Title not available (Why is that?)

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)