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 previous tests can influence the tests 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 ${\displaystyle n}$ items must take ${\displaystyle n\log(n)}$ comparisons. For comparison sorts, a query is a comparison of two items ${\displaystyle a,\,b}$, with two outcomes (assuming no items are equal): either ${\displaystyle a<b}$ or ${\displaystyle a>b}$. 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. ^[1]

For example, many sorting algorithms are comparison sorts, which means that they only gain information about an input sequence ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ via local comparisons: testing whether ${\displaystyle x_{i}<x_{j}}$, ${\displaystyle x_{i}=x_{j}}$, or ${\displaystyle x_{i}>x_{j}}$. Assuming that the items to be sorted are all distinct and comparable, this can be rephrased as a yes-or-no question: is ${\displaystyle x_{i}>x_{j}}$?

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 ${\displaystyle \pi }$ that describes how the input sequence was scrambled from the fully ordered list of items. (The inverse of this permutation, ${\displaystyle \pi ^{-1}}$, re-orders the input sequence.)

One can show that comparison sorts must use ${\displaystyle \Omega (n\log(n))}$ comparisons through a simple argument: for an algorithm to be correct, it must be able to output every possible permutation of ${\displaystyle n}$ 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: ${\displaystyle n!}$ leaves. Any binary tree with at least ${\displaystyle n!}$ leaves has depth at least ${\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}$, 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. ^{[2] : 91}

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 ${\displaystyle \log _{2}(n!)}$ 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 ${\displaystyle n}$ 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 ${\displaystyle n-1}$ comparisons to find the minimum. (The information-theoretic argument here only gives a lower bound of ${\displaystyle \log(n)}$.) A similar argument works for general lower bounds for computing order statistics. ^{[2] : 214}

Linear and algebraic decision trees

Linear decision trees generalize the above comparison decision trees to computing functions that take real vectors ${\displaystyle x\in \mathbb {R} ^{n}}$ as input. The tests in linear decision trees are linear functions: for a particular choice of real numbers ${\displaystyle a_{0},\dots ,a_{n}}$, output the sign of ${\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}$. (Algorithms in this model can only depend on the sign of the output.) Comparison trees are linear decision trees, because the comparison between ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$ corresponds to the linear function ${\displaystyle x_{i}-x_{j}}$. From its definition, linear decision trees can only specify functions ${\displaystyle f}$ 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 ${\displaystyle d}$. Geometrically, the space is divided into semi-algebraic sets (a generalization of hyperplane).

These decision tree models, defined by Rabin ^[3] and Reingold, ^[4] are often used for proving lower bounds in computational geometry. ^[5] For example, Ben-Or showed that element uniqueness (the task of computing ${\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}}$, where ${\displaystyle f(x)}$ is 0 if and only if there exist distinct coordinates ${\displaystyle i,j}$ such that ${\displaystyle x_{i}=x_{j}}$) requires an algebraic decision tree of depth ${\displaystyle \Omega (n\log(n))}$. ^[6] This was first showed for linear decision models by Dobkin and Lipton. ^[7] They also show a ${\displaystyle n^{2}}$ lower bound for linear decision trees on the knapsack problem, generalized to algebraic decision trees by Steele and Yao. ^[8]

Boolean decision tree complexities

For Boolean decision trees, the task is to compute the value of an n-bit Boolean function ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$ for an input ${\displaystyle x\in \{0,1\}^{n}}$. The queries correspond to reading a bit of the input, ${\displaystyle x_{i}}$, and the output is ${\displaystyle f(x)}$. 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 ${\displaystyle f(x)}$, for all ${\displaystyle x\in \{0,1\}^{n}}$, the decision tree is said to "compute" ${\displaystyle f}$. The depth of a tree is the maximum number of queries that can happen before a leaf is reached and a result obtained. ${\displaystyle D(f)}$, the deterministic decision tree complexity of ${\displaystyle f}$ is the smallest depth among all deterministic decision trees that compute ${\displaystyle f}$.

Randomized decision tree

One way to define a randomized decision tree is to add additional nodes to the tree, each controlled by a probability ${\displaystyle p_{i}}$. 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. ${\displaystyle R_{2}(f)}$ is defined as the complexity of the lowest-depth randomized decision tree whose result is ${\displaystyle f(x)}$ with probability at least ${\displaystyle 2/3}$ for all ${\displaystyle x\in \{0,1\}^{n}}$ (i.e., with bounded 2-sided error).

${\displaystyle R_{2}(f)}$ 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 ${\displaystyle R_{0}(f)}$ 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 ${\displaystyle R_{1}(f)}$.

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 ${\displaystyle f}$ at ${\displaystyle x}$ is the size of the smallest subset of indices ${\displaystyle S\subset [n]}$ such that, for all ${\displaystyle y\in \{0,1\}^{n}}$, if ${\displaystyle y_{i}=x_{i}}$ for all ${\displaystyle i\in S}$, then ${\displaystyle f(y)=f(x)}$. The certificate complexity of ${\displaystyle f}$ is the maximum certificate complexity over all ${\displaystyle x}$. The analogous notion where one only requires the verifier to be correct with 2/3 probability is denoted ${\displaystyle RC(f)}$.

Quantum decision tree

The quantum decision tree complexity ${\displaystyle Q_{2}(f)}$ is the depth of the lowest-depth quantum decision tree that gives the result ${\displaystyle f(x)}$ with probability at least ${\displaystyle 2/3}$ for all ${\displaystyle x\in \{0,1\}^{n}}$. Another quantity, ${\displaystyle Q_{E}(f)}$, is defined as the depth of the lowest-depth quantum decision tree that gives the result ${\displaystyle f(x)}$ with probability 1 in all cases (i.e. computes ${\displaystyle f}$ exactly). ${\displaystyle Q_{2}(f)}$ and ${\displaystyle Q_{E}(f)}$ 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 ${\displaystyle Q_{0}(f)}$ and ${\displaystyle Q_{1}(f)}$.

These notions are typically bounded by the notions of degree and approximate degree. The degree of ${\displaystyle f}$, denoted ${\displaystyle \deg(f)}$, is the smallest degree of any polynomial ${\displaystyle p}$ satisfying ${\displaystyle f(x)=p(x)}$ for all ${\displaystyle x\in \{0,1\}^{n}}$. The approximate degree of ${\displaystyle f}$, denoted ${\displaystyle {\widetilde {\deg }}(f)}$, is the smallest degree of any polynomial ${\displaystyle p}$ satisfying ${\displaystyle p(x)\in [0,1/3]}$ whenever ${\displaystyle f(x)=0}$ and ${\displaystyle p(x)\in [2/3,1]}$ whenever ${\displaystyle f(x)=1}$.

Beals et al. established that ${\displaystyle Q_{0}(f)\geq \deg(f)/2}$ and ${\displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}$. ^[9]

Relationships between boolean function complexity measures

It follows immediately from the definitions that for all ${\displaystyle n}$-bit Boolean functions ${\displaystyle f}$,${\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}$, and ${\displaystyle Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n}$. 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, ^[10] Hartmanis and Hemachandra, ^[11] and Tardos ^[12] independently discovered that ${\displaystyle D(f)\leq R_{0}(f)^{2}}$. Noam Nisan found that the Monte Carlo randomized decision tree complexity is also polynomially related to deterministic decision tree complexity: ${\displaystyle D(f)=O(R_{2}(f)^{3})}$. ^[13] (Nisan also showed that ${\displaystyle D(f)=O(R_{1}(f)^{2})}$.) A tighter relationship is known between the Monte Carlo and Las Vegas models: ${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$. ^[14] This relationship is optimal up to polylogarithmic factors. ^[15] As for quantum decision tree complexities, ${\displaystyle D(f)=O(Q_{2}(f)^{4})}$, and this bound is tight. ^{[16] [15]} Midrijanis showed that ${\displaystyle D(f)=O(Q_{0}(f)^{3})}$, ^{[17] [18]} improving a quartic bound due to Beals et al. ^[9]

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 ${\displaystyle \{0,1\}^{n}}$, an exponential separation between ${\displaystyle Q_{0}(f)}$ and ${\displaystyle D(f)}$ is possible; the first example of such a problem was discovered by Deutsch and Jozsa.

Sensitivity conjecture

For a Boolean function ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$, the sensitivity of ${\displaystyle f}$ is defined to be the maximum sensitivity of ${\displaystyle f}$ over all ${\displaystyle x}$, where the sensitivity of ${\displaystyle f}$ at ${\displaystyle x}$ is the number of single-bit changes in ${\displaystyle x}$ that change the value of ${\displaystyle f(x)}$. Sensitivity is related to the notion of total influence from the analysis of Boolean functions, which is equal to average sensitivity over all ${\displaystyle x}$.

The sensitivity conjecture is the conjecture that sensitivity is polynomially related to query complexity; that is, there exists exponent ${\displaystyle c,c'}$ such that, for all ${\displaystyle f}$, ${\displaystyle D(f)=O(s(f)^{c})}$ and ${\displaystyle s(f)=O(D(f)^{c'})}$. One can show through a simple argument that ${\displaystyle s(f)\leq D(f)}$, 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 ${\displaystyle f}$, denoted ${\displaystyle bs(f)}$, is defined to be the maximum block sensitivity of ${\displaystyle f}$ over all ${\displaystyle x}$. The block sensitivity of ${\displaystyle f}$ at ${\displaystyle x}$ is the maximum number ${\displaystyle t}$ of disjoint subsets ${\displaystyle S_{1},\ldots ,S_{t}\subset [n]}$ such that, for any of the subsets ${\displaystyle S_{i}}$, flipping the bits of ${\displaystyle x}$ corresponding to ${\displaystyle S_{i}}$ changes the value of ${\displaystyle f(x)}$. ^[13]

Since block sensitivity takes a maximum over more choices of subsets, ${\displaystyle s(f)\leq bs(f)}$. Further, block sensitivity is polynomially related to the previously discussed complexity measures; for example, Nisan's paper introducing block-sensitivity showed that ${\displaystyle bs(f)\leq D(f)=O(bs(f)^{4})}$. ^[13] So, one could rephrase the sensitivity conjecture as showing that, for some ${\displaystyle c}$, ${\displaystyle bs(f)=O(s(f)^{c})}$. In 1992, Nisan and Szegedy conjectured that ${\displaystyle c=2}$ suffices. ^[19] This would be tight, as Rubinstein in 1995 showed a quadratic separation between sensitivity and block sensitivity. ^[20]

In July 2019, 27 years after the conjecture was initially posed, Hao Huang from Emory University proved the sensitivity conjecture, showing that ${\displaystyle bs(f)=O(s(f)^{4})}$. ^[21] This proof is notably succinct, proving this statement in two pages when prior progress towards the sensitivity conjecture had been limited. ^{[22] [23]}

Summary of known results

Best-known separations for complexity measures as of October 2020 ^{[update] [16]}

	${\displaystyle D}$	${\displaystyle R_{0}}$	${\displaystyle R_{2}}$	${\displaystyle C}$	${\displaystyle RC}$	${\displaystyle bs}$	${\displaystyle s}$	${\displaystyle Q_{0}}$	${\displaystyle \deg }$	${\displaystyle Q}$	${\displaystyle {\widetilde {\deg }}}$
${\displaystyle D}$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
${\displaystyle R_{0}}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
${\displaystyle R}$	1	1		2	2, 3	2, 3	3, 6	1.5, 3	2, 3	3, 4	4
${\displaystyle C}$	1	1	1, 2		2	2	2.22, 5	1.15, 3	1.63, 3	2, 4	2, 4
${\displaystyle RC}$	1	1	1	1		1.5, 2	2, 4	1.15, 2	1.63, 2	2	2
${\displaystyle bs}$	1	1	1	1	1		2, 4	1.15, 2	1.63, 2	2	2
${\displaystyle s}$	1	1	1	1	1	1		1.15, 2	1.63, 2	2	2
${\displaystyle Q_{0}}$	1	1.33, 2	1.33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
${\displaystyle \deg }$	1	1.33, 2	1.33, 2	2	2	2	2	1		2	2
${\displaystyle Q}$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
${\displaystyle {\widetilde {\deg }}}$	1	1	1	2	2	2	2	1	1	1

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 ${\displaystyle A}$-th row and ${\displaystyle B}$-th column denotes bounds on the exponent ${\displaystyle c}$, which is the infimum of all ${\displaystyle k}$ satisfying ${\displaystyle A(f)=O(B(f)^{k})}$ for all boolean functions ${\displaystyle f}$. For example, the entry in the D-th row and s-th column is "3, 6", so ${\displaystyle D(f)=O(\operatorname {s} (f)^{6+o(1)})}$ for all ${\displaystyle f}$, and there exists a function ${\displaystyle g}$ such that ${\displaystyle D(g)=\Omega (\operatorname {s} (g)^{3-o(1)})}$.

See also

• Comparison sort
• Decision tree
• Aanderaa–Karp–Rosenberg conjecture
• Minimum spanning tree § Decision trees

References

1. Ford, Lester R. Jr.; Johnson, Selmer M. (1959-05-01). "A Tournament Problem". The American Mathematical Monthly. 66 (5): 387–389. doi:10.1080/00029890.1959.11989306. ISSN   0002-9890.
2. Introduction to algorithms. Cormen, Thomas H. (Third ed.). Cambridge, Mass.: MIT Press. 2009. ISBN   978-0-262-27083-0. OCLC   676697295.
3. Rabin, Michael O. (1972-12-01). "Proving simultaneous positivity of linear forms". Journal of Computer and System Sciences. 6 (6): 639–650. doi: 10.1016/S0022-0000(72)80034-5 . ISSN   0022-0000.
4. Reingold, Edward M. (1972-10-01). "On the Optimality of Some Set Algorithms". Journal of the ACM. 19 (4): 649–659. doi: 10.1145/321724.321730 . ISSN   0004-5411. S2CID   18605212.
5. Preparata, Franco P. (1985). Computational geometry : an introduction. Shamos, Michael Ian. New York: Springer-Verlag. ISBN   0-387-96131-3. OCLC   11970840.
6. Ben-Or, Michael (1983-12-01). "Lower bounds for algebraic computation trees". Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83. STOC '83. New York, NY, USA: Association for Computing Machinery. pp. 80–86. doi: 10.1145/800061.808735 . ISBN   978-0-89791-099-6. S2CID   1499957.
7. Dobkin, David; Lipton, Richard J. (1976-06-01). "Multidimensional Searching Problems". SIAM Journal on Computing. 5 (2): 181–186. doi:10.1137/0205015. ISSN   0097-5397.
8. Michael Steele, J; Yao, Andrew C (1982-03-01). "Lower bounds for algebraic decision trees". Journal of Algorithms. 3 (1): 1–8. doi:10.1016/0196-6774(82)90002-5. ISSN   0196-6774.
9. Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "Quantum lower bounds by polynomials". Journal of the ACM. 48 (4): 778–797. arXiv: quant-ph/9802049 . doi:10.1145/502090.502097. S2CID   1078168.
10. Blum, M.; Impagliazzo, R. (1987). "Generic oracles and oracle classes". Proceedings of 18th IEEE FOCS. pp. 118–126.
11. Hartmanis, J.; Hemachandra, L. (1987), "One-way functions, robustness, and non-isomorphism of NP-complete sets", Technical Report DCS TR86-796, Cornell University
12. Tardos, G. (1989). "Query complexity, or why is it difficult to separate NP^A ∩ coNP^A from P^A by random oracles A?". Combinatorica. 9 (4): 385–392. doi:10.1007/BF02125350. S2CID   45372592.
13. Nisan, N. (1989). "CREW PRAMs and decision trees". Proceedings of 21st ACM STOC. pp. 327–335.
14. Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.
15. Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (2017-09-04). "Separations in Query Complexity Based on Pointer Functions". Journal of the ACM. 64 (5): 32:1–32:24. arXiv: 1506.04719 . doi:10.1145/3106234. ISSN   0004-5411. S2CID   10214557.
16. Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (2020-10-23). "Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem". arXiv: 2010.12629 [quant-ph].
17. Midrijanis, Gatis (2004), "Exact quantum query complexity for total Boolean functions", arXiv: quant-ph/0403168
18. Midrijanis, Gatis (2005), "On Randomized and Quantum Query Complexities", arXiv: quant-ph/0501142
19. Nisan, Noam; Szegedy, Mario (1992-07-01). "On the degree of Boolean functions as real polynomials". Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92. STOC '92. Victoria, British Columbia, Canada: Association for Computing Machinery. pp. 462–467. doi: 10.1145/129712.129757 . ISBN   978-0-89791-511-3. S2CID   6919144.
20. Rubinstein, David (1995-06-01). "Sensitivity vs. block sensitivity of Boolean functions". Combinatorica. 15 (2): 297–299. doi:10.1007/BF01200762. ISSN   1439-6912. S2CID   41010711.
21. Huang, Hao (2019). "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture". Annals of Mathematics. 190 (3): 949–955. arXiv: 1907.00847 . doi:10.4007/annals.2019.190.3.6. ISSN   0003-486X. JSTOR   10.4007/annals.2019.190.3.6. S2CID   195767594.
22. Klarreich, Erica. "Decades-Old Computer Science Conjecture Solved in Two Pages". Quanta Magazine. Retrieved 2019-07-26.
23. Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (2011-06-22). "Variations on the Sensitivity Conjecture". Theory of Computing. 1: 1–27. doi: 10.4086/toc.gs.2011.004 . ISSN   1557-2862. S2CID   6918061.

Surveys

• Buhrman, Harry; de Wolf, Ronald (2002), "Complexity Measures and Decision Tree Complexity: A Survey" (PDF), Theoretical Computer Science, 288 (1): 21–43, doi: 10.1016/S0304-3975(01)00144-X