Decision tree model

In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of "queries" or "tests" that are done adaptively, so the outcome of the previous tests can influence the test is performed next.
Typically, these tests have a small number of outcomes (such as a yes-no question) and can be performed quickly (say, with unit computational cost), so the worst-case time complexity of an algorithm in the decision tree model corresponds to the depth of the corresponding decision tree. This notion of computational complexity of a problem or an algorithm in the decision tree model is called its decision tree complexity or query complexity.
Decision trees models are instrumental in establishing lower bounds for complexity theory for certain classes of computational problems and algorithms. Several variants of decision tree models have been introduced, depending on the computational model and type of query algorithms are allowed to perform.
For example, a decision tree argument is used to show that a comparison sort of formula_1 items must take formula_2 comparisons. For comparison sorts, a query is a comparison of two items formula_3, with two outcomes (assuming no items are equal): either formula_4 or formula_5. Comparison sorts can be expressed as a decision tree in this model, since such sorting algorithms only perform these types of queries.
Comparison trees and lower bounds for sorting.
Decision trees are often employed to understand algorithms for sorting and other similar problems; this was first done by Ford and Johnson.
For example, many sorting algorithms are comparison sorts, which means that they only gain information about an input sequence formula_6 via local comparisons: testing whether formula_7, formula_8, or formula_9. Assuming that the items to be sorted are all distinct and comparable, this can be rephrased as a yes-or-no question: is formula_9?
These algorithms can be modeled as binary decision trees, where the queries are comparisons: an internal node corresponds to a query, and the node's children correspond to the next query when the answer to the question is yes or no. For leaf nodes, the output corresponds to a permutation formula_11 that describes how the input sequence was scrambled from the fully ordered list of items. (The inverse of this permutation, formula_12, re-orders the input sequence.)
One can show that comparison sorts must use formula_13 comparisons through a simple argument: for an algorithm to be correct, it must be able to output every possible permutation of formula_1 elements; otherwise, the algorithm would fail for that particular permutation as input. So, its corresponding decision tree must have at least as many leaves as permutations: formula_15 leaves. Any binary tree with at least formula_15 leaves has depth at least formula_17, so this is a lower bound on the run time of a comparison sorting algorithm. In this case, the existence of numerous comparison-sorting algorithms having this time complexity, such as mergesort and heapsort, demonstrates that the bound is tight.
This argument does not use anything about the type of query, so it in fact proves a lower bound for any sorting algorithm that can be modeled as a binary decision tree. In essence, this is a rephrasing of the information-theoretic argument that a correct sorting algorithm must learn at least formula_18 bits of information about the input sequence. As a result, this also works for randomized decision trees as well.
Other decision tree lower bounds do use that the query is a comparison. For example, consider the task of only using comparisons to find the smallest number among formula_1 numbers. Before the smallest number can be determined, every number except the smallest must "lose" (compare greater) in at least one comparison. So, it takes at least formula_20 comparisons to find the minimum. (The information-theoretic argument here only gives a lower bound of formula_21.) A similar argument works for general lower bounds for computing order statistics.
Linear and algebraic decision trees.
Linear decision trees generalize the above comparison decision trees to computing functions that take real vectors formula_22 as input. The tests in linear decision trees are linear functions: for a particular choice of real numbers formula_23, output the sign of formula_24. (Algorithms in this model can only depend on the sign of the output.) Comparison trees are linear decision trees, because the comparison between formula_25 and formula_26 corresponds to the linear function formula_27. From its definition, linear decision trees can only specify functions formula_28 whose fibers can be constructed by taking unions and intersections of half-spaces.
"Algebraic decision trees" are a generalization of linear decision trees that allow the test functions to be polynomials of degree formula_29. Geometrically, the space is divided into semi-algebraic sets (a generalization of hyperplane).
These decision tree models, defined by Rabin and Reingold, are often used for proving lower bounds in computational geometry. For example, Ben-Or showed that element uniqueness (the task of computing formula_30, where formula_31 is 0 if and only if there exist distinct coordinates formula_32 such that formula_8) requires an algebraic decision tree of depth formula_13. This was first showed for linear decision models by Dobkin and Lipton. They also show a formula_35 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 formula_36 for an input formula_37. The queries correspond to reading a bit of the input, formula_25, and the output is formula_31. 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 formula_31, for all formula_41, the decision tree is said to "compute" formula_28. The depth of a tree is the maximum number of queries that can happen before a leaf is reached and a result obtained. formula_43, the "deterministic decision tree" complexity of formula_28 is the smallest depth among all deterministic decision trees that compute formula_28.
Randomized decision tree.
One way to define a "randomized decision tree" is to add additional nodes to the tree, each controlled by a probability formula_46. 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. formula_47 is defined as the complexity of the lowest-depth randomized decision tree whose result is formula_31 with probability at least formula_49 for all formula_41 (i.e., with bounded 2-sided error).
formula_47 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 formula_52 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 formula_53.
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 formula_28 at formula_55 is the size of the smallest subset of indices formula_56 such that, for all formula_57, if formula_58 for all formula_59, then formula_60. The certificate complexity of formula_28 is the maximum certificate complexity over all formula_55. The analogous notion where one only requires the verifier to be correct with 2/3 probability is denoted formula_63.
Quantum decision tree.
The quantum decision tree complexity formula_64 is the depth of the lowest-depth quantum decision tree that gives the result formula_31 with probability at least formula_49 for all formula_67. Another quantity, formula_68, is defined as the depth of the lowest-depth quantum decision tree that gives the result formula_31 with probability 1 in all cases (i.e. computes formula_28 exactly). formula_64 and formula_68 are more commonly known as "quantum query complexities", because the direct definition of a quantum decision tree is more complicated than in the classical case. Similar to the randomized case, we define formula_73 and formula_74.
These notions are typically bounded by the notions of degree and approximate degree. The "degree" of formula_28, denoted formula_76, is the smallest degree of any polynomial formula_77 satisfying formula_78 for all formula_37. The "approximate degree" of formula_28, denoted formula_81, is the smallest degree of any polynomial formula_77 satisfying formula_83 whenever formula_84 and formula_85 whenever formula_86.
Beals et al. established that formula_87 and formula_88.
Relationships between boolean function complexity measures.
It follows immediately from the definitions that for all formula_1-bit Boolean functions formula_28,formula_91, and formula_92. Finding the best upper bounds in the converse direction is a major goal in the field of query complexity.
All of these types of query complexity are polynomially related. Blum and Impagliazzo, Hartmanis and Hemachandra, and Tardos independently discovered that formula_93. Noam Nisan found that the Monte Carlo randomized decision tree complexity is also polynomially related to deterministic decision tree complexity: formula_94. (Nisan also showed that formula_95.) A tighter relationship is known between the Monte Carlo and Las Vegas models: formula_96. This relationship is optimal up to polylogarithmic factors. As for quantum decision tree complexities, formula_97, and this bound is tight. Midrijanis showed that formula_98, improving a quartic bound due to Beals et al.
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 formula_99, an exponential separation between formula_73 and formula_43 is possible; the first example of such a problem was discovered by Deutsch and Jozsa.
Sensitivity conjecture.
For a Boolean function formula_36, the "sensitivity" of formula_28 is defined to be the maximum sensitivity of formula_28 over all formula_55, where the sensitivity of formula_28 at formula_55 is the number of single-bit changes in formula_55 that change the value of formula_31. Sensitivity is related to the notion of total influence from the analysis of Boolean functions, which is equal to "average" sensitivity over all formula_55.
The sensitivity conjecture is the conjecture that sensitivity is polynomially related to query complexity; that is, there exists exponent formula_111 such that, for all formula_28, formula_113 and formula_114. One can show through a simple argument that formula_115, so the conjecture is specifically concerned about finding a lower bound for sensitivity. Since all of the previously-discussed complexity measures are polynomially related, the precise type of complexity measure is not relevant. However, this is typically phrased as the question of relating sensitivity with block sensitivity.
The "block sensitivity" of formula_28, denoted formula_117, is defined to be the maximum block sensitivity of formula_28 over all formula_55. The block sensitivity of formula_28 at formula_55 is the maximum number formula_122 of disjoint subsets formula_123 such that, for any of the subsets formula_124, flipping the bits of formula_55 corresponding to formula_124 changes the value of formula_31.
Since block sensitivity takes a maximum over more choices of subsets, formula_128. Further, block sensitivity is polynomially related to the previously discussed complexity measures; for example, Nisan's paper introducing block-sensitivity showed that formula_129. So, one could rephrase the sensitivity conjecture as showing that, for some formula_130, formula_131. In 1992, Nisan and Szegedy conjectured that formula_132 suffices. This would be tight, as Rubinstein in 1995 showed a quadratic separation between sensitivity and block sensitivity.
In July 2019, 27 years after the conjecture was initially posed, Hao Huang from Emory University proved the sensitivity conjecture, showing that formula_133. This proof is notably succinct, proving this statement in two pages when prior progress towards the sensitivity conjecture had been limited.
Summary of known results.
This table summarizes results on separations between Boolean function complexity measures. The complexity measures are, in order, deterministic, zero-error randomized, two-sided-error randomized, certificate, randomized certificate, block sensitivity, sensitivity, exact quantum, degree, quantum, and approximate degree complexities.
The number in the formula_134-th row and formula_135-th column denotes bounds on the exponent formula_130, which is the infimum of all formula_137 satisfying formula_138 for all boolean functions formula_28. For example, the entry in the D-th row and s-th column is "3, 6", so formula_140 for all formula_28, and there exists a function formula_142 such that formula_143.