Karl Jones: Created page with "In computational complexity and communication complexity theories, the '''decision tree model''' is the model of computation or com..."

2016-12-06T20:52:25Z

Created page with "In computational complexity and communication complexity theories, the '''decision tree model''' is the model of computation or com..."

New page

In [[Computational complexity theory|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.

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. Every query is 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 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.

he computation complexity of a problem or an algorithm expressed in terms of the decision tree model is called decision tree complexity or query complexity.

== See also ==

* [[Analysis of algorithms]]
* [[Communication complexity]]
* [[Computational complexity theory]]
* [[Decision tree]]
* [[Minimum spanning tree]]

== External links ==

* [https://en.wikipedia.org/wiki/Decision_tree_model Decision tree model] @ Wikipedia

[[Category:Complexity]]
[[Category:Computation]]

Decision tree model - Revision history

Karl Jones: Created page with "In computational complexity and communication complexity theories, the '''decision tree model''' is the model of computation or com..."