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 branching operations based on comparisons of some quantities, the comparisons being assigned unit computational cost.
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 where the input is a series of queries and the output is the final decision. Each query may be dependent on previous queries.
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 complexity theory for certain classes of computational problems and algorithms. The computational complexity of a problem or an algorithm expressed in terms of the decision tree model is called its decision tree complexity or query complexity.
- ^“Data structures and algorithms, by Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
- ^ Jump up to:ab Blum, M.; Impagliazzo, R. (1987). “Generic oracles and oracle classes”. Proceedings of 18th IEEE FOCS. pp. 118–126.
- ^ Jump up to:ab Hartmanis, J.; Hemachandra, L. (1987), “One-way functions, robustness, and non-isomorphism of NP-complete sets”, Technical Report DCS TR86-796, Cornell University
- ^ Jump up to:ab Tardos, G. (1989). “Query complexity, or why is it difficult to separate NPA ∩ coNPA from PA by random oracles A?”. Combinatorica. 9: 385–392. doi:10.1007/BF02125350.
- ^ Jump up to:ab c Nisan, N. (1989). “CREW PRAMs and decision trees”. Proceedings of 21st ACM STOC. pp. 327–335.
- ^ Jump up to:ab Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.
- ^Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troy; Santha, Miklos; Smotrovs, Juris (2015). “Separations in Query Complexity Based on Pointer Functions”. arXiv:1506.04719 [cs.CC].
- ^Midrijanis, Gatis (2004), “Exact quantum query complexity for total Boolean functions”, arXiv:quant-ph/0403168
- ^ Jump up to:abc Midrijanis, Gatis (2005), “On Randomized and Quantum Query Complexities”, arXiv:quant-ph/0501142
- ^ Jump up to:abc 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.
- ^ Buhrman, R. Cleve, R. de Wolf, and Ch. Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms. In 40th IEEE Symposium on Foundations of Computer Science (FOCS’99), pp.358-368. cs.CC/9904019, 1999.
- ^ Aaronson. Quantum Certificate Complexity. IEEE Conference on Computational Complexity, pp. 171-178, 2003.