A decision problem is a disjoint partition Rn = S1 [ ? ? ? [ Sq of Rn into arbitrary sets Si. A decision tree T for a decision problem is a binary tree whose internal nodes are labeled by predicates defined on Rn, whose outgoing edges of an internal node are labeled by true or false, and whose leaves are labeled by one of the Si (Fig. 3.1 shows an example). The evaluation of T on input x 2 Rn starts at the root and then proceeds downwards by evaluating the predicate at an internal node and taking the appropriate of the two outgoing edges. Finally, a leaf with label Sx is reached. Sx is the result of the computation, the path x followed is the computation path of x, and T is correct if x 2 Sx for all x. The worst-case running time of T is the length of the longest computation path in T .

T is called an algebraic decision tree if all functions evaluated at internal nodes are defined by polynomials. The most restricted algebraic decision trees are comparison trees where only comparisons between two input variables are allowed ([FG], [MT]). Linear decision trees ([Sn82]) where linear functions of the input variables can be used ([BLY], [DL], [FG], [MT], [RY]) are more powerful. Products of linear functions were used in [Y89]) and arbitrary polynomials of bounded degree in [Be] and [Y92]. Finally, arbitrary analytic functions were allowed in [Ja] and [Rab]. Of course, this classification of algebraic decision trees is not exhaustive and many less natural restrictions on the functions can be found in the literature (e.g. [DL], [MMS]).

In our paper, we only prove lower bounds for algebraic decision trees, but we also want to mention the algebraic computation tree model where additional computing nodes exist which evaluate elementary functions on all input variables and previously computed functions ([Be], [OD]). Of course, this can be simulated by an algebraic decision tree which uses polynomials of increasing degree, but this model is much closer to the model of "real" algorithms (e.g. [PS]). Probabilistic and nondeterministic decision trees have also been studied ([MT], [Sn85]).

From now on, we assume that the decision problem is a membership problem, i.e. we want to decide whether an input x 2 Rn is in a set S ? Rn (we call S the target set), but the lower bounds mentioned below can easily be transformed into similar bounds for arbitrary decision problems. Several lower bound techniques are known for algebraic decision trees. One of the first and most widely used arguments was that the logarithm of the number of connected components of S is a lower bound for the depth of linear decision trees ([DL]. This was generalized in [Be] to bounded degree decision trees. And recently Ramanan has shown how this technique can sometimes give strong lower bounds even for sets S which do not have many connected components by intersecting S with another easily computable set and thus increasing the number of components ([Ram]). Another old approach is to use an adversary argument to show that there must be at least one long path in the tree ([DL]) or proving the existence of many disjoint subtrees ([FG]).

An interesting topological lower bound, at least for linear decision trees, was proved by Rivest and Yao. They showed that the logarithm of the number of s-dimensional faces of S for arbitrary s is a lower bound ([RY]). And very recently, Yao et. al. have found a way to exploit even a much more complex topological property of S, i.e. they showed that the logarithm of the Euler characteristic of S is a lower bound not only for linear decision trees ([BLY]) but also for bounded degree decision trees ([Y92]).