Topological lower bounds for arithmetic networks
| Autor: | Nicolai Vorobjov, Andrei Gabrielov |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics Semialgebraic set Betti number General Mathematics Sigma 010103 numerical & computational mathematics Computational Complexity (cs.CC) Homology (mathematics) Binary logarithm Mathematics::Algebraic Topology 01 natural sciences Upper and lower bounds Theoretical Computer Science Combinatorics Computer Science - Computational Complexity Mathematics - Algebraic Geometry Computational Mathematics Computational Theory and Mathematics Bounded function FOS: Mathematics 0101 mathematics Arithmetic Algebraic Geometry (math.AG) Mathematics |
| Zdroj: | Gabrielov, A & Vorobjov, N 2017, ' Topological lower bounds for arithmetic networks ', Computational Complexity, vol. 26, no. 3, pp. 687-715 . https://doi.org/10.1007/s00037-016-0145-8 |
| ISSN: | 1420-8954 1016-3328 |
| DOI: | 10.1007/s00037-016-0145-8 |
| Popis: | 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. 19 pages, 10 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink