Lower bound on testing membership to a polyhedron by algebraic decision and computation trees. (English) Zbl 0871.68176

Summary: We introduce a new method of proving lower bounds on the depth of algebraic \(d\)-degree decision (resp. computation) trees and apply it to prove a lower bound \(\Omega(\log N)\) (resp. \(\Omega(\log N/\log\log N))\) for testing membership to an \(n\)-dimensional convex polyhedron having \(N\) faces of all dimensions, provided that \(N>(nd)^{\Omega(n)}\) (resp. \(N>n^{\Omega(n)}\). This bound apparently does not follow from the methods developed by Ben-Or, Björner, Lovasz, and Yao because topological invariants used in these methods become trivial for convex polyhedra.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI


[1] M. Ben-Or, Lower bounds for algebraic computation trees,Proceedings of ACM Symposium on Theory of Computing, 1983, pp. 80-86.
[2] Björner, A.; Joseph, A. (ed.), Subspace arrangements,Proceedings of 1st European Congress of Mathematics, Paris, 321-370 (1994), Basel · Zbl 0844.52008
[3] A. Björner and L. Lovasz, Linear decision trees, subspace arrangements and Möbius functions, Preprint, 1992. · Zbl 0811.05070
[4] A. Björner, L. Lovasz, and A. Yao, Linear decision trees: Volume estimates and topological bounds,Proceedings of ACM Symposium on Theory of Computing, 1992, pp. 170-177.
[5] P. Buergisser, M. Karpinski, and T. Lickteig, On randomized algebraic test complexity, Technical Report TR-92-070, International Computer Science Institute, Berkeley, CA, 1992.
[6] M. Goresky and R. MacPherson,Stratified Morse Theory, Springer-Verlag, Berlin, 1988. · Zbl 0639.14012
[7] D. Grigoriev, Complexity of deciding Tarski algebra,J. Symbolic Comput., 5 (1988), 65-108. · Zbl 0689.03021 · doi:10.1016/S0747-7171(88)80006-3
[8] D. Grigoriev, M. Karpinski, and M. Singer, Computational complexity of sparse real algebraic function interpolation.Proceedings MEGA ’92, Progress in Mathematics, Vol.109, Birkhäuser, Basel, 1993, pp. 91-104. · Zbl 0801.68087
[9] D. Grigoriev, M. Karpinski, and N. Vorobjov, Lower bounds on testing membership to a polyhedron by algebraic decision trees,Proceedings of ACM Symposium on Theory of Computing, 1994, pp. 635-644. · Zbl 1345.68158
[10] D. Grigoriev and N. Vorobjov, Solving systems of polynomial inequalities in subexponential time,J. Symbolic Comput., 5 (1988), 37-64. · Zbl 0662.12001
[11] D. Grigoriev and N. Vorobjov, Counting connected components of a semialgebraic set in subexponential time,Comput. Complexity, 2 (1992), 133-186. · Zbl 0900.68253
[12] D. Grigoriev and N. Vorobjov, Complexity lower bounds for computation trees with elementary transcendental function gates,Proceedings of IEEE Symposium on Foundations of Computer Science, 1994, pp. 48-552. Also inTheoret. Comput. Sci.,157 (1996), 185-214. · Zbl 0877.68086
[13] M. Hirsch,Differential Topology, Springer-Verlag, New York, 1976. · Zbl 0356.57001
[14] S. Lang,Algebra, Addison-Wesley, Reading, MA, 1965. · Zbl 0193.34701
[15] Loos, R.; Buchberger, B. (ed.), Generalized polynomial remainder sequences, 115-136 (1982), New York
[16] P. McMullen and G. Shephard,Convex Polythopes and the Upper Bound Conjecture, Cambridge University Press, Cambridge, 1971. · Zbl 0217.46702
[17] F. Meyer auf der Heide, Fast algorithms for n-dimensional restrictions of hard problems,Proceedings of ACM Symposium on Theory of Computing, 1985, pp. 413-420.
[18] J. Milnor, On the Betti numbers of real varieties,Proc. Amer. Math. Soc.15 (1964), 275-280. · Zbl 0123.38302 · doi:10.2307/2034050
[19] J. L. Montana, J. E. Morais, and L. M. Pardo, Lower bounds for arithmetic networks, 2: sum of Betti numbers,Appl. Algebra Engrg. Comm. Comput. 7 (1996), 41-51. · Zbl 0844.68069 · doi:10.1007/BF01613615
[20] M.-F. Roy and N. Vorobjov, Finding irreducible components of some real transcendental varieties,Comput. Complexity 4 (1994), 107-132. · Zbl 0808.68065 · doi:10.1007/BF01202285
[21] A. Tarski,A Decision Method for Elementary Algebra and Geometry, University of California Press, Berkeley, CA, 1951. · Zbl 0044.25102
[22] J. A. Thorpe,Elementary Topics in Differential Geometry, Springer-Verlag, Berlin, 1977.
[23] A. Yao, Algebraic decision trees and Euler characteristics,Proceedings of IEEE Symposium on Foundations of Computer Science, 1992, pp. 268-277. · Zbl 0977.68556
[24] A. Yao, Decision tree complexity and Betti numbers.Proceedings of ACM Symposium on Theory of Computing, 1994, pp. 615-624. · Zbl 1345.68297
[25] A. Yao and R. Rivest, On the polyhedral decision problem,S1AM J. Comput. 9 (1980), 343-347. · Zbl 0447.68076 · doi:10.1137/0209028
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.