is 0 if and only if there exist distinct coordinates such that ) requires an algebraic decision tree of depth . This was first showed for linear decision models by Dobkin and Lipton. They also show a lower bound for linear decision trees on the knapsack problem, generalized to algebraic decision trees by Steele and Yao. Boolean decision tree complexities For Boolean decision trees, the task is to compute the value of an n-bit Boolean function for an input . The queries correspond to reading a bit of the input, , and the output is . Each query may be dependent on previous queries. There are many types of computational models using decision trees that could be considered, admitting multiple complexity notions, called complexity measures. Deterministic decision tree If the output of a decision tree is , for all , the decision tree is said to "compute" . The depth of a tree is the maximum number of queries that can happen before a leaf is reached and a result obtained. , the deterministic decision tree complexity of is the smallest depth among all deterministic decision trees that compute . Randomized decision tree One way to define a randomized decision tree is to add additional nodes to the tree, each controlled by a probability . Another equivalent definition is to define it as a distribution over deterministic decision trees. Based on this second definition, the complexity of the randomized tree is defined as the largest depth among all the trees in the support of the underlying distribution. is defined as the complexity of the lowest-depth randomized decision tree whose result is with probability at least for all (i.e., with bounded 2-sided error). is known as the Monte Carlo randomized decision-tree complexity, because the result is allowed to be incorrect with bounded two-sided error. The Las Vegas decision-tree complexity measures the expected depth of a decision tree that must be correct (i.e., has zero-error). There is also a one-sided bounded-error version which is denoted by . Nondeterministic decision tree The nondeterministic decision tree complexity of a function is known more commonly as the certificate complexity of that function. It measures the number of input bits that a nondeterministic algorithm would need to look at in order to evaluate the function with certainty. Formally, the certificate complexity of at is the size of the smallest subset of indices such that, for all