Complexity lower bounds for computation trees with elementary transcendental function gates
D. Grigoriev, Nicolai Vorobjov · 2002
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 /spl Omega/(/spl radic/(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 previous approaches adopted for algebraic computation trees.>