Lower bound on testing membership to a polyhedron by algebraic decision and computation trees |
| |
| Authors: | D Grigoriev M Karpinski N Vorobjov |
| |
| Institution: | (1) Departments of Computer Science and Mathematics, Perm State University, 16802 University Park, PA, USA;(2) Department of Computer Science, University of Bonn, 53117 Bonn, Germany;(3) International Computer Science Institute, 94704 Berkeley, CA, USA;(4) School of Mathematical Sciences, University of Bath, Avon BA2 7AY, Bath, England |
| |
| Abstract: | We introduce a new method of proving lower bounds on the depth of algebraicd-degree decision (resp. computation) trees and apply it to prove a lower bound Ω (logN) (resp. Ω (log N/log logN)) for testing membership to an n-dimensional convex polyhedron havingN faces of all dimensions, provided thatN > (nd)Ω(n) (resp.N > nΩ(n)). This bound apparently does not follow from the methods developed by Ben-Or, Björner, Lovasz, and Yao 1], 4], 24] because topological invariants used in these methods become trivial for convex polyhedra |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
