Topological lower bounds for arithmetic networks. (English) Zbl 1379.68150
Summary: We prove that the depth of any arithmetic network for deciding membership in a semialgebraic set \(\Sigma \subset \mathbb{R}^{n}\) is bounded from below by
\[
c_1 \sqrt{ \frac{\log ({\mathrm b}(\Sigma))}{n}} -c_2 \log n,
\]
where \({\mathrm b}(\Sigma)\) is the sum of the Betti numbers of \(\Sigma\) with respect to “ordinary” (singular) homology, and \(c_1\), \(c_2\) are some (absolute) positive constants. This result complements the similar lower bound in [J. L. Montaña et al., Appl. Algebra Eng. Commun. Comput. 7, No. 1, 41–51 (1996; Zbl 0844.68069)] for locally closed semialgebraic sets in terms of the sum of Borel-Moore Betti numbers. {
}We also prove that if \(\rho: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n-r}\) is the projection map, for some \(r=0, \dots, n\), then the depth of any arithmetic network deciding membership in \(\Sigma\) is bounded by
\[
\frac{c_1\sqrt{\log ({\mathrm b}(\rho(\Sigma)))}}{n} - c_2 \log n
\]
for some positive constants \(c_1\), \(c_2\).
MSC:
68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
14P10 | Semialgebraic sets and related spaces |
14P25 | Topology of real algebraic varieties |
14Q20 | Effectivity, complexity and computational aspects of algebraic geometry |
Citations:
Zbl 0844.68069References:
[1] | P. Bürgisser & F. Cucker (2005). Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré. In Complexity of Computations and Proofs (Jan Krajicek ed.), volume 13 of Quaderini di Matematica, 73-152. · Zbl 1076.68033 |
[2] | Gabrielov A., Vorobjov N. (2005) Betti numbers of semialgebraic sets defined by quantifier-free formulae. Discrete Comput. Geom. 33(3): 395-401 · Zbl 1073.14072 · doi:10.1007/s00454-004-1105-7 |
[3] | Gabrielov A., Vorobjov N. (2009) Approximation of definable sets by compact families, and upper bounds on homotopy and homology. J. London Math. Soc. 80(2): 493-496 · Zbl 1177.14097 |
[4] | A. Gabrielov & N. Vorobjov (2015). On topological lower bounds for algebraic computation trees. Found. Comput. Math., doi:10.1007/s10208-015-9283-7. · Zbl 1365.14080 |
[5] | Gabrielov A., Vorobjov N., Zell T. (2004) Betti numbers of semialgebraic and sub-Pfaffian sets. J. London Math. Soc. 69(2): 27-43 · Zbl 1087.14038 · doi:10.1112/S0024610703004939 |
[6] | J. von zur Gathen (1986). Parallel arithmetic computations: a survey. In Proceedings of the 12th Symposium Bratislava, Czechoslovakia August 25-29, 1986 (J. Gruska, B. Rovan, J. Wiedermann eds.), 93-112. Springer Lecture Notes in Computer Science, 233. · Zbl 0616.68037 |
[7] | Montaña J.L., Morais J.E., Pardo L.M. (1996) Lower bounds for arithmetic networks II: sum of Betti numbers. Appl. Algebra Engrg. Comm. Comput. 7: 41-51 · Zbl 0844.68069 · doi:10.1007/BF01613615 |
[8] | Montaña J.L., Pardo L.M. (1993) Lower bounds for arithmetic networks. Appl. Algebra Engrg. Comm. Comput. 4: 1-24 · Zbl 0769.68055 · doi:10.1007/BF01270397 |
[9] | Yao A.C.C. (1997) Decision tree complexity and Betti numbers. J. Comput. Syst. Sci. 55: 36-43 · Zbl 0880.68100 · doi:10.1006/jcss.1997.1495 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.