Difference between revisions of "Decision tree complexity"
| Line 1: | Line 1: | ||
For <math>x \in \{-1,1\}^n</math> we let <math>c(A, x)</math> be the number of queries that the [[decision tree]] ''A'' (also called algorithm) asks when the input to ''f'' is ''x''. Let <math>c(A) := \max_x c(A, x)</math> be the maximum number of queries that ''A'' makes which we view as the cost of ''A'' on ''f''. This is the same as the depth of the [[decision tree]]; the maximum distance of a leaf from the root. The deterministic complexity (also called the decision tree complexity) of a Boolean function ''f'', denoted by ''D(f)'', is the minimum of ''c(A)'' over all deterministic algorithms ''A'' for ''f'', so that <math>D(f) = \min_A \max_x c(A,x).</math><ref>Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.</ref> | For <math>x \in \{-1,1\}^n</math> we let <math>c(A, x)</math> be the number of queries that the [[decision tree]] ''A'' (also called algorithm) asks when the input to ''f'' is ''x''. Let <math>c(A) := \max_x c(A, x)</math> be the maximum number of queries that ''A'' makes which we view as the cost of ''A'' on ''f''. This is the same as the depth of the [[decision tree]]; the maximum distance of a leaf from the root. The deterministic complexity (also called the decision tree complexity) of a Boolean function ''f'', denoted by ''D(f)'', is the minimum of ''c(A)'' over all deterministic algorithms ''A'' for ''f'', so that <math>D(f) = \min_A \max_x c(A,x).</math><ref>Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.</ref> | ||
It can be shown that if <math>D(f)=n</math> if and only if the function ''f'' is [[evasive]]. | It can be shown that if <math>D(f)=n</math> if and only if the function ''f'' is [[evasive]]. | ||
| + | |||
| + | This is one of many notions of complexity such as [[randomized complexity]] and [[level-p-comlexity]]. | ||
Revision as of 15:29, 19 March 2022
For [math]x \in \{-1,1\}^n[/math] we let [math]c(A, x)[/math] be the number of queries that the decision tree A (also called algorithm) asks when the input to f is x. Let [math]c(A) := \max_x c(A, x)[/math] be the maximum number of queries that A makes which we view as the cost of A on f. This is the same as the depth of the decision tree; the maximum distance of a leaf from the root. The deterministic complexity (also called the decision tree complexity) of a Boolean function f, denoted by D(f), is the minimum of c(A) over all deterministic algorithms A for f, so that [math]D(f) = \min_A \max_x c(A,x).[/math][1] It can be shown that if [math]D(f)=n[/math] if and only if the function f is evasive.
This is one of many notions of complexity such as randomized complexity and level-p-comlexity.
- ↑ Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation. Vol. 5. Cambridge University Press, 2014.
