In computational complexity and communication complexity theories the decision tree model is the model of computation or communication in which an algorithm or communication process is considered to be basically a decision tree, i.e., a sequence of branching operations based on comparisons of some quantities, the comparisons being assigned the unit computational cost.
Contents
- Simple decision tree
- Linear decision tree
- Algebraic decision tree
- Deterministic decision tree
- Randomized decision tree
- Nondeterministic decision tree
- Quantum decision tree
- Relationship between different models
- References
The branching operations are called "tests" or "queries". In this setting the algorithm in question may be viewed as a computation of a Boolean function
Several variants of decision tree models have been introduced, depending on the complexity of the operations allowed in the computation of a single comparison and the way of branching.
Decision trees models are instrumental in establishing lower bounds for computational complexity for certain classes of computational problems and algorithms: the lower bound for worst-case computational complexity is proportional to the largest depth among the decision trees for all possible inputs for a given computational problem. The computation complexity of a problem or an algorithm expressed in terms of the decision tree model is called decision tree complexity or query complexity.
Simple decision tree
The model in which every decision is based on the comparison of two numbers within constant time is called simply a decision tree model. It was introduced to establish computational complexity of sorting and searching.
The simplest illustration of this lower bound technique is for the problem of finding the smallest number among n numbers using only comparisons. In this case the decision tree model is a binary tree. Algorithms for this searching problem may result in n different outcomes (since any of the n given numbers may turn out to be the smallest one). It is known that the depth of a binary tree with n leaves is at least
However this lower bound is known to be slack, since the following simple argument shows that at least n - 1 comparisons are needed: Before the smallest number can be determined, every number except the smallest must "lose" (compare greater) in at least one comparison.
Along the same lines the lower bound of
Linear decision tree
Linear decision trees, just like the simple decision trees, make a branching decision based on a set of values as input. As opposed to binary decision trees, linear decision trees have three output branches. A linear function
Geometrically,
Algebraic decision tree
Algebraic decision trees are a generalization of linear decision trees to allow test functions to be polynomials of degree d. Geometrically, the space is divided into semi-algebraic sets (a generalization of hyperplane). The evaluation of the complexity is more difficult.
Deterministic decision tree
If the output of a decision tree is
Randomized decision tree
One way to define a randomized decision tree is to add additional nodes to the tree, each controlled by a probability
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.
Quantum decision tree
The quantum decision tree complexity
Relationship between different models
It follows immediately from the definitions that for all
Blum and Impagliazzo, Hartmanis and Hemachandra, and Tardos independently discovered that
The quantum decision tree complexity
It is important to note that these polynomial relationships are valid only for total Boolean functions. For partial Boolean functions, that have a domain a subset of
These relationships can be summarized by the following inequalities, which are true up to constant factors: