Decision tree model on arvau

Wikipedia / Decision tree model

In computational complexity theory, the decision tree model is the model of computation in which an algorithm can be considered to be 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 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 tree models are instrumental in establishing lower bounds for the complexity of 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. Comparison sorts can be expressed as decision trees 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?

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, re-orders the input sequence.)

leaves. Any binary tree, 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 bits of information about the input sequence. As a result, this also works for randomized decision trees as well.

.) 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 whose fibers can be constructed by taking unions and intersections of half-spacess.

Algebraic decision trees are a generalization of linear decision trees that allow the test functions to be polynomials. Geometrically, the space is divided into semialgebraic sets (a generalization of a hyperplane).

These decision tree models, defined by Rabin and Reingold, are often used for proving lower bounds in computational geometry. For example, Ben-Or is 0 if and only if. This was first shown for linear decision models by Dobkin and Lipton. 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. 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

. The depth of a tree is the maximum number of queries that can happen before a leaf is reached and a result obtained. , the deterministic decision tree.

Randomized decision tree

One way to define a randomized decision tree. 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. (i.e., with bounded 2-sided error).

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 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 .

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 . Another quantity, are more commonly known as quantum query complexities.

These notions are typically bounded by the notions of degree and approximate degree. The degree. The approximate degree.

Relationships between Boolean function complexity measures

. 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. Noam Nisan.. This relationship is optimal up to polylogarithmic factors., and this bound is tight., improving a quartic bound due to Beals et al.

These polynomial relationships are valid only for total Boolean functions. For partial Boolean functions is possible; the first example of such a problem was discovered by Deutsch and Jozsa.

Sensitivity conjecture

For a Boolean function, the sensitivity. Sensitivity is related to the notion of total influence from the analysis of Boolean functions, which is equal to average.

The sensitivity conjecture, 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.

In 2019, Hao Huang.