Topological lower bounds for arithmetic networks

DOI10.1007/S00037-016-0145-8MaRDI QIDQ2410689zbMATH OpenOpenAlexFDO

Authors Andrei Gabrielov, Nicolai Vorobjov

Publication date 18 October 2017

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.03387, http://opus.bath.ac.uk/51147/1/networkCC060116.pdf

zbMATH Keywords

semialgebraic setscomplexity lower boundsarithmetic networks

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 a complexity lower bound on deciding membership in a semialgebraic set for arithmetic networks in terms of the sum of Betti numbers with respect to "ordinary" (singular) homology. This result complements a similar lower bound by Montana, Morais and Pardo for locally close semialgebraic sets in terms of the sum of Borel-Moore Betti numbers. We also prove a lower bound in terms of the sum of Betti numbers of the projection of a semialgebraic set to a coordinate subspace.

Recommendations

• Lower bounds for arithmetic networks
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• Bounding the number of arithmetical structures on graphs
• scientific article; zbMATH DE number 4187085
• scientific article; zbMATH DE number 528937
• Lower bounds for topological complexity
• A sorting network in bounded arithmetic
• Topological lower bounds on algebraic random access machines
• scientific article; zbMATH DE number 503392
• Circuit lower bounds in bounded arithmetics

Cites work

• scientific article; zbMATH DE number 3999284 (Why is no real title available?)
• 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
• Lower bounds for arithmetic networks
• Lower bounds for arithmetic networks. II: Sum of Betti numbers
• On topological lower bounds for algebraic computation trees

Cited in

(2)

• On the number of homotopy types of fibres of a definable map
• Lower bounds for arithmetic networks

This page was built for publication: Topological lower bounds for arithmetic networks

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