Lower bounds for arithmetic networks. II: Sum of Betti numbers. (English) Zbl 0844.68069
Summary: [For part I see ibid. 4, No. 1, 1-24 (1993; Zbl 0769.68055).]
We show lower bounds for the parallel complexity and membership problems in semialgebraic sets. Our lower bounds are obtained from the Euler characteristic and the sum of Betti numbers. We remark that these lower bounds are polynomial (an square root) in the sequential lower bounds obtained by Andrew C. C. Yao.
We show lower bounds for the parallel complexity and membership problems in semialgebraic sets. Our lower bounds are obtained from the Euler characteristic and the sum of Betti numbers. We remark that these lower bounds are polynomial (an square root) in the sequential lower bounds obtained by Andrew C. C. Yao.
MSC:
| 68W30 | Symbolic computation and algebraic computation |
| 68Q25 | Analysis of algorithms and problem complexity |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
Citations:
Zbl 0769.68055References:
| [1] | Ben-Or. M.: Lower bound for algebraic computation trees. A.C.M. 15 th Symposium on Theory of Computation, 80–86 (1983) |
| [2] | Björner, A., Lovász, L.: Linear decision trees, subspace arrangements and Möbis function. Preprint (1992) |
| [3] | Björner, A., Lovász, L., Yao, A.: Linear decision trees: volume estimates and topological bounds. In: Proc. A.C.M. 24 th Symposium on Theory of Computing, 170–177 (1992) |
| [4] | Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin A.M.S.21(1), 1–46 (1989) · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9 |
| [5] | Bochnack, J., Cost, M., Roy, M-F: Géométrie algébrique réelle. Ergebnisse der Math., 3. Folge, Band12, Berlin, Heidelberg, New York: Springer (1987) |
| [6] | Cucker, F.:P\(\mathbb{R}\)C\(\mathbb{R}\). To appear in: J. of Complexity · Zbl 1307.68037 |
| [7] | Cucker, F., Montana, J.L., Pardo, L.M.: Time Bounded Computations over the reals. Int. J. Alg. Comp.2(4), 395–408 (1992) · Zbl 0788.68043 · doi:10.1142/S0218196792000244 |
| [8] | Dobkin, O.P., Lipton, R.J.: On the complexity of computations under varying sets of primitives. J. Comp. Syst. Sci.18, 86–91 (1979) · Zbl 0409.68023 · doi:10.1016/0022-0000(79)90054-0 |
| [9] | Von, J., zur Gathen: Parallel arithmetic computations: a survey. In: Math. Found comput. Sci. 13 th Proc. (1986) · Zbl 0616.68037 |
| [10] | Fitchas, N., Galligo, A., Morgenstern, J.: Algorithmes rapides en séquentiel et en parallèle pour l’élimination de quantificateurs en géométrie élémentair. Seminaire de Structures Algebriques Ordennes, Université de Paris VII (1987) |
| [11] | Greenberg, M.J., Harper, J.R.: Algebraic Topology: A first course. Mathematics lecture note series 58. The Benjamin/Cummings Publishing Company, (1981) · Zbl 0498.55001 |
| [12] | Grigorev, D.: Complexity of deciding Tarski algebra. J. Symb. Comp.5, 65–108 (1988) · Zbl 0689.03021 · doi:10.1016/S0747-7171(88)80006-3 |
| [13] | Heintz, J.: Definability and fast quantifier elimination over algebraically closed fields. Theor. Comp. Sci.24, 239–278 (1983) · Zbl 0546.03017 · doi:10.1016/0304-3975(83)90002-6 |
| [14] | Heintz, J., Roy, M.-F., Solernó, P.: Sur la Complexité du Principe de Tarski-Seidenbrg. Bull. Soc. Math. France118, 101–126 (1990) |
| [15] | Milnor, J.: On the Betti numbers of real varieties. Proc. Am. Math. Soc.15, 275–280 (1964) · Zbl 0123.38302 · doi:10.1090/S0002-9939-1964-0161339-9 |
| [16] | Montaña, J.L., Pardo, L.M.: Lower bounds for Arithmetic Networks. AAECC4, 1–24 (1993) · Zbl 0769.68055 · doi:10.1007/BF01270397 |
| [17] | Montaña, J.L., Luis M. Pardo y T. Recio: The Non-Scalar Model of Complexity in Computational Semialgebraic Geometry. In: Proc MEGA’90, Progress in Mathematics vol 94, Birkhäuser, 346–362 (1991) · Zbl 0762.14027 |
| [18] | Preparata, F.P., Shamos, M.I.: Computational Geometry, An Introduction. Texts and Monographs in Computer Science. Berlin, Heidelberg, New York: Springer (1985) · Zbl 0575.68059 |
| [19] | Smale, S.: On the topology of Algorithms, I. J Complexity3, 81–89 (1987) · Zbl 0639.68042 · doi:10.1016/0885-064X(87)90021-5 |
| [20] | Steele, M., Yao, A.: Lower bounds for Algebraic Decision Trees. J. Algorithms3, 1–8 (1982) · Zbl 0477.68065 · doi:10.1016/0196-6774(82)90002-5 |
| [21] | Yao, A.: Algebraic Decision trees and Euler characteristics. Proceedings of 33rd Annual IEEE on Foundations of Computer Science, 268–277 (1992) · Zbl 0977.68556 |
| [22] | Yao, A.C.C.: Decision trees and Betti Numbers. To appear in Proc. STOCS’94 (1994) |
| [23] | Yao, F.F.: Computational Geometry. In: Handbook of Theoretical Computer Science. J. van Leeuwen, ed., Elsevier, Amsterdam 343–391 (1990) |
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.
