Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates (Extended abstract)
Dima Grigoriev · 1994
We consider computation trees which admit as gate functions along with the usual arithmetic operations also algebraic or transcendental functions like exp; log; sin; square root (defined in the relevant domains) or much more general, Pfaffian functions. A new method for proving lower bounds on the depth of these trees is developed which allows to prove a lower bound \\Omega\\Gamma p log N ) for testing membership to a convex polyhedron with N facets of all dimensions, provided that N is large enough. This method differs essentially from the approaches adopted for algebraic computation trees ([1], [4], [26], [13]). 1 Pfaffian computation trees We consider the following computation model, a generalization of the algebraic computation trees (see, e.g., [1], [26]). Definition 1. Pfaffian computation tree T is a tree at every node v of which a Pfaffian function f v in variables X 1 ; : : : ; Xn is attached, which satisfies the following properties. Let f v0 ; : : : ; f v l ; f v l+1 = ...