Modelo de árbol de decisión

Si la salida de un árbol de decisión es ${\displaystyle f(x)}$, para todos ${\displaystyle x\in \{0,1\}^{n}}$, se dice que el árbol de decisión "calcula" ${\displaystyle f}$ . La profundidad de un árbol es el número máximo de consultas que pueden ocurrir antes de que se alcance una hoja y se obtenga un resultado. ${\displaystyle D(f)}$, la complejidad del árbol de decisión determinista de ${\displaystyle f}$ es la profundidad más pequeña entre todos los árboles de decisión deterministas que calculan ${\displaystyle f}$ .

Una forma de definir un árbol de decisión aleatorio es agregando nodos adicionales al árbol, cada uno controlado por una probabilidad ${\displaystyle p_{i}}$ . Otra definición equivalente lo construye como una distribución sobre árboles de decisión deterministas. Con base en esta segunda definición, la complejidad del árbol aleatorio se define como la mayor profundidad entre todos los árboles en el soporte de la distribución subyacente. ${\displaystyle R_{2}(f)}$ se define como la complejidad del árbol de decisión aleatorio de menor profundidad cuyo resultado es ${\displaystyle f(x)}$ con probabilidad al menos ${\displaystyle 2/3}$ para todos ${\displaystyle x\in \{0,1\}^{n}}$ (es decir, con error de dos colas acotado).

${\displaystyle R_{2}(f)}$ se conoce como la complejidad del árbol de decisión aleatorio de Monte Carlo, porque se permite que el resultado sea incorrecto con un error de dos colas acotado. La complejidad del árbol de decisión de Las Vegas ${\displaystyle R_{0}(f)}$ mide la profundidad esperada de un árbol de decisión que debe ser correcto (es decir, tiene cero errores). También hay una versión de error acotado unilateral que se denota por ${\displaystyle R_{1}(f)}$ .

La complejidad del árbol de decisión no determinista de una función se conoce más comúnmente como la complejidad del certificado de esa función. Mide la cantidad de bits de entrada que un algoritmo no determinista necesitaría consultar para evaluar la función con certeza.

Formalmente, la complejidad del certificado de ${\displaystyle f}$ a ${\displaystyle x}$ es el tamaño del subconjunto más pequeño de índices ${\displaystyle S\subset [n]}$ tal que, por todo ${\displaystyle y\in \{0,1\}^{n}}$, si ${\displaystyle y_{i}=x_{i}}$ para todos ${\displaystyle i\in S}$, después ${\displaystyle f(y)=f(x)}$ . La complejidad del certificado de ${\displaystyle f}$ es la complejidad máxima del certificado sobre todos ${\displaystyle x}$ . La noción análoga en la que solo se requiere que el verificador sea correcto con 2/3 de probabilidad se denota ${\displaystyle RC(f)}$ .

La complejidad del árbol de decisión cuántico ${\displaystyle Q_{2}(f)}$ es la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado ${\displaystyle f(x)}$ con probabilidad al menos ${\displaystyle 2/3}$ para todo ${\displaystyle x\in \{0,1\}^{n}}$ . Otra cantidad, denominada ${\displaystyle Q_{E}(f)}$, está definida como la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado ${\displaystyle f(x)}$ con probabilidad 1 en todos los casos (es decir, calcula ${\displaystyle f}$ exactamente). ${\displaystyle Q_{2}(f)}$ y ${\displaystyle Q_{E}(f)}$ se conocen más comúnmente como complejidades de consulta cuántica, porque la definición directa de un árbol de decisión cuántica es más complicada que en el caso clásico. Similar al caso aleatorio, definimos ${\displaystyle Q_{0}(f)}$ y ${\displaystyle Q_{1}(f)}$ .

Estas nociones suelen estar acotadas por las nociones de grado y grado aproximado. El grado de ${\displaystyle f}$, denotado ${\displaystyle \deg(f)}$, es el grado más pequeño de cualquier polinomio ${\displaystyle p}$ que satisface ${\displaystyle f(x)=p(x)}$ para toda ${\displaystyle x\in \{0,1\}^{n}}$ . El grado aproximado de ${\displaystyle f}$, denotado ${\displaystyle {\widetilde {\deg }}(f)}$, es el grado más pequeño de cualquier polinomio ${\displaystyle p}$ que satisface ${\displaystyle p(x)\in [0,1/3]}$ cuando ${\displaystyle f(x)=0}$ y ${\displaystyle p(x)\in [2/3,1]}$ cuando ${\displaystyle f(x)=1}$ .

Beals et al. estableció que ${\displaystyle Q_{0}(f)\geq {\frac {\deg(f)}{2}}}$ y ${\displaystyle Q_{2}(f)\geq {\frac {{\widetilde {\deg }}(f)}{2}}}$ .[9]

Para una función booleana ${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$, la sensibilidad de ${\displaystyle f}$ se define como la máxima sensibilidad de ${\displaystyle f}$ en cualquier ${\displaystyle x}$, donde la sensibilidad de ${\displaystyle f}$ en ${\displaystyle x}$ es el número de cambios de un solo bit en ${\displaystyle x}$ que cambia el valor de ${\displaystyle f(x)}$ . La sensibilidad está relacionada con la noción de influencia total del análisis de funciones booleanas, que es igual a la sensibilidad promedio sobre todos los valores ${\displaystyle x}$ .

La conjetura de sensibilidad dice que la sensibilidad está polinomialmente relacionada con la complejidad de consulta; es decir, existen exponentes ${\displaystyle c,c'}$ tales que, para toda ${\displaystyle f}$, ${\displaystyle D(f)=O(s(f)^{c})}$ y ${\displaystyle s(f)=O(D(f)^{c'})}$ . Uno puede mostrar a través de un argumento simple que ${\displaystyle s(f)\leq D(f)}$, por lo que la conjetura se ocupa específicamente de encontrar una cuota inferior para la sensibilidad. Dado que todas las medidas de complejidad discutidas anteriormente están relacionadas polinómicamente, el tipo preciso de medida de complejidad no es relevante. Sin embargo, esto normalmente se expresa como la cuestión de relacionar la sensibilidad con la sensibilidad de bloque.

La sensibilidad de bloque de ${\displaystyle f}$, denotado ${\displaystyle bs(f)}$, se define como la máxima sensibilidad de bloque de ${\displaystyle f}$ en cualquiera ${\displaystyle x}$ . La sensibilidad de bloque de ${\displaystyle f}$ en ${\displaystyle x}$ es el número máximo ${\displaystyle t}$ de subconjuntos disjuntos ${\displaystyle S_{1},\ldots ,S_{t}\subset [n]}$ tal que, para cualquiera de los subconjuntos ${\displaystyle S_{i}}$, volteando los pedacitos de ${\displaystyle x}$ correspondiente a ${\displaystyle S_{i}}$ cambia el valor de ${\displaystyle f(x)}$ .[13]

Dado que la sensibilidad de bloque toma su máximo valor en más opciones de subconjuntos, ${\displaystyle s(f)\leq bs(f)}$ . Además, la sensibilidad de bloque está relacionada polinómicamente con las medidas de complejidad discutidas previamente; por ejemplo, el artículo de Nisan que introdujo la sensibilidad a los bloques mostró que ${\displaystyle bs(f)\leq D(f)=O(bs(f)^{4})}$ .[13] Por lo tanto, uno podría reformular la conjetura de la sensibilidad mostrando que, para algunos ${\displaystyle c}$, ${\displaystyle bs(f)=O(s(f)^{c})}$ . En 1992, Nisan y Szegedy conjeturaron que ${\displaystyle c=2}$ es suficiente [16] Esto sería un valor escrio, ya que Rubinstein en 1995 mostró una separación cuadrática entre la sensibilidad y la sensibilidad de bloque.[17]

En julio de 2019, 27 años después de que se planteó inicialmente la conjetura, Hao Huang, de la Universidad de Emory, demostró la conjetura de la sensibilidad, mostrando que ${\displaystyle bs(f)=O(s(f)^{4})}$ .[18] Esta prueba es notablemente sucinta. Huang prueba esto en dos páginas, mientras que el progreso previo hacia la conjetura de sensibilidad había sido limitado.[19][20]

Mejores separaciones conocidas para medidas de complejidad a 31 de octubre de 2020

	${\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

Esta tabla resume los resultados de las separaciones entre las medidas de complejidad de funciones booleanas. Las medidas de complejidad son, en orden, complejidades deterministas, aleatorias con cero errores, aleatorias con errores bilaterales, certificado, certificado aleatorio, sensibilidad de bloque, sensibilidad, cuántico exacto, grado, cuántica, y grado aproximado.

El número en la ${\displaystyle A}$ -ésima fila y ${\displaystyle B}$ -ésima columna denota las cuotas en el exponente ${\displaystyle c}$, que es el ínfimo de toda ${\displaystyle k}$ que satisface ${\displaystyle A(f)=O(B(f)^{k})}$ para todas las funciones booleanas ${\displaystyle f}$ . Por ejemplo, la entrada en la D-ésima fila y la s-ésima columna es "3, 6", por lo que ${\displaystyle D(f)=O(\operatorname {s} (f)^{6+o(1)})}$ para toda ${\displaystyle f}$, y existe una función ${\displaystyle g}$ tal que ${\displaystyle D(g)=\Omega (\operatorname {s} (g)^{3-o(1)})}$ .

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