Modelo de árbol de decisión

En complejidad computacional el modelo de árbol de decisión es el modelo de computación en que un algoritmo es considerado básicamente como un árbol de decisión, i.e., una secuencia de consultas o pruebas que se realizan adaptativamente, así que el resultado de las pruebas anteriores puede influir la prueba que se realiza después.

Por lo general, estas pruebas tienen una pequeña cantidad de resultados (tales como preguntas de sí o no) y se pueden realizar rápidamente (por ejemplo, con un costo computacional unitario), por lo que la complejidad temporal de un algoritmo en el peor de los casos en el modelo de árbol de decisión corresponde a la profundidad del árbol de decisión correspondiente. Esta noción de complejidad computacional de un problema o un algoritmo en el modelo de árbol de decisión se denomina complejidad del árbol de decisión o complejidad de consulta .

Los modelos de árboles de decisión son fundamentales para establecer cuotas inferiores para la teoría de la complejidad para ciertas clases de problemas y algoritmos computacionales. Se han introducido varias variantes de modelos de árboles de decisión, según el modelo computacional y el tipo de algoritmos de consulta que se les permite realizar.

Por ejemplo, un argumento de árbol de decisión se usa para mostrar que un ordenamiento por comparación de $n$ objetos debe tomar $n\log(n)$ comparaciones. Para ordenamientos por comparación, una consulta es una comparación de dos elementos $a,\,b$, con dos resultados (suponiendo que ningún par de elementos sean iguales): $a<b$ o $a>b$ . Los ordenamientos por comparación se pueden expresar como un árbol de decisión en este modelo, ya que dichos algoritmos de ordenamiento solo realizan este tipo de consultas.

Árboles de comparación y cuotas inferiores para ordenamientos

Los árboles de decisión a menudo se emplean para comprender los algoritmos de ordenamiento y otros problemas similares; esto fue hecho por primera vez por Ford y Johnson.​

Por ejemplo, muchos algoritmos de ordenamiento son ordenamientos por comparación, lo que significa que solo obtienen información sobre una secuencia de entrada. $x_{1},x_{2},\ldots ,x_{n}$ a través de comparaciones locales: probando si $x_{i}<x_{j}$, $x_{i}=x_{j}$, o $x_{i}>x_{j}$ . Suponiendo que los elementos a clasificar son todos distintos y comparables, esto se puede reformular como una pregunta de sí o no: ¿es $x_{i}>x_{j}$ ?

Estos algoritmos se pueden modelar como árboles de decisión binarios, donde las consultas son comparaciones: un nodo interno corresponde a una consulta y los hijos del nodo corresponden a la siguiente consulta cuando la respuesta a la pregunta es sí o no. Para los nodos hoja, el resultado corresponde a una permutación $\pi$ que describe cómo se codificó la secuencia de entrada de la lista completa de elementos ordenados. (El inverso de esta permutación, $\pi ^{-1}$, reordena la secuencia de entrada. )

Se puede mostrar que los ordenamientos de comparación deben usar $\Omega (n\log(n))$ comparaciones a través de un argumento simple: para que un algoritmo sea correcto, debe poder generar todas las permutaciones posibles de $n$ elementos; de lo contrario, el algoritmo fallaría para esa permutación particular como entrada. Entonces, su árbol de decisión correspondiente debe tener al menos tantas hojas como permutaciones, es decir, $n!$ hojas. Cualquier árbol binario con al menos $n!$ hojas tendrá una profundidad de al menos $\log _{2}(n!)=\Omega (n\log _{2}(n))$, por lo que este es un límite inferior en el tiempo de ejecución de un algoritmo de ordenamiento por comparación. En este caso, la existencia de numerosos algoritmos de ordenamiento por comparación que tienen esta complejidad de tiempo, como ordenamiento por mezcla (mergesort) y heapsort, demuestra que la cuota es rígida.​

Este argumento no utiliza nada acerca del tipo de consulta, por lo que, de hecho, demuestra una cuota inferior para cualquier algoritmo de ordenamiento que pueda modelarse como un árbol de decisión binario. En esencia, esta es una reformulación del argumento en teoría de la información de que un algoritmo de clasificación correcto debe aprender al menos $\log _{2}(n!)$ bits de información sobre la secuencia de entrada. Como resultado, esto también funciona para árboles de decisión aleatorios.

Otras cuotas inferiores para el modelo de árbol de decisión utilizan que la consulta es una comparación. Por ejemplo, considera la tarea de usar solo comparaciones para encontrar el número más pequeño entre $n$ números. Antes de que se pueda determinar el número más pequeño, todos los números excepto el más pequeño deben "perder" (comparar mayor) en al menos una comparación. Entonces, se necesita al menos $n-1$ comparaciones para encontrar el mínimo. (El argumento teórico de la información aquí solo da una cuota inferior de $\log(n)$ . ) Un argumento similar funciona para las cuotas inferiores generales para calcular estadísticos de orden .​

Árboles de decisión lineales y algebraicos

Los árboles de decisión lineales generalizan los árboles de decisión de comparación anteriores para computar funciones que toman vectores reales $x\in \mathbb {R} ^{n}$ como entradas. Las pruebas en árboles de decisión lineales son funciones lineales: para una elección particular de números reales $a_{0},\dots ,a_{n}$, emite el signo de $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$ . (Los algoritmos en este modelo solo pueden depender del signo de la salida. ) Los árboles de comparación son árboles de decisión lineales, porque la comparación entre $x_{i}$ y $x_{j}$ corresponde a la función lineal $x_{i}-x_{j}$ . Por su definición, los árboles de decisión lineales solo pueden especificar funciones $f$ cuyas fibras se pueden construir tomando uniones e intersecciones de semiespacios.

Los árboles de decisión algebraicos son una generalización de los árboles de decisión lineales que permiten que las funciones de prueba sean polinomios de grado $d$ . Geométricamente, el espacio se divide en conjuntos semialgebráicos (una generalización del hiperplano).

Estos modelos de árboles de decisión, definidos por Rabin​ y Reingold,​ se utilizan a menudo para demostrar cuotas inferiores en geometría computacional .​ Por ejemplo, Ben-Or demostró que la unicidad de los elementos (la tarea de calcular $f:\mathbb {R} ^{n}\to \{0,1\}$, dónde $f(x)$ es 0 si y solo si existen coordenadas distintas $i,j$ tal que $x_{i}=x_{j}$ ) requiere un árbol de decisión algebraico de profundidad $\Omega (n\log(n))$ .​ Esto fue mostrado por primera vez para los modelos de decisión lineal por Dobkin y Lipton.​ También muestran una cuota inferior de $n^{2}$ para árboles de decisión lineales en el problema de la mochila, generalizado a árboles de decisión algebraicos por Steele y Yao.​

Complejidades del árboles de decisión booleanos

Para árboles de decisión Booleana, la tarea es calcular el valor de una función booleana de $n$ bits $f:\{0,1\}^{n}\to \{0,1\}$ para una entrada $x\in \{0,1\}^{n}$ . Las consultas corresponden a leer un bit de la entrada, $x_{i}$, y la salida es $f(x)$ . Cada consulta puede depender de las consultas anteriores. Son muchos los tipos de modelos computacionales que utilizan árboles de decisión que se podrían considerar, admitiendo múltiples nociones de complejidad, denominadas medidas de complejidad .

Árbol de decisión determinista

Si la salida de un árbol de decisión es $f(x)$, para todos $x\in \{0,1\}^{n}$, se dice que el árbol de decisión "calcula" $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. $D(f)$, la complejidad del árbol de decisión determinista de $f$ es la profundidad más pequeña entre todos los árboles de decisión deterministas que calculan $f$ .

Árbol de decisión aleatorizada

Una forma de definir un árbol de decisión aleatorio es agregando nodos adicionales al árbol, cada uno controlado por una probabilidad $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. $R_{2}(f)$ se define como la complejidad del árbol de decisión aleatorio de menor profundidad cuyo resultado es $f(x)$ con probabilidad al menos $2/3$ para todos $x\in \{0,1\}^{n}$ (es decir, con error de dos colas acotado).

$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 $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 $R_{1}(f)$ .

Árbol de decisión no determinista

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

Árbol de decisión cuántica

La complejidad del árbol de decisión cuántico $Q_{2}(f)$ es la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado $f(x)$ con probabilidad al menos $2/3$ para todo $x\in \{0,1\}^{n}$ . Otra cantidad, denominada $Q_{E}(f)$, está definida como la profundidad del árbol de decisión cuántico de menor profundidad que da el resultado $f(x)$ con probabilidad 1 en todos los casos (es decir, calcula $f$ exactamente). $Q_{2}(f)$ y $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 $Q_{0}(f)$ y $Q_{1}(f)$ .

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

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

Relaciones entre medidas de complejidad de funciones booleanas

Se sigue inmediatamente de las definiciones que para toda funcn Booleana de $f$,

$Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$,

y

$Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n$ .

Encontrar las mejores posibles cuotas superiores en la dirección inversa es un objetivo importante en el campo de complejidad de consultas.

Todos estos tipos de complejidad de consulta están relacionados polinómicamente. Blum e Impagliazzo,​ Hartmanis y Hemachandra,​ y Tardos​ descubrieron de forma independiente que $D(f)\leq R_{0}(f)^{2}$ . Noam Nisan descubrió que la complejidad del árbol de decisión aleatorio de Monte Carlo también está relacionada polinómicamente con la complejidad del árbol de decisión determinista de la siguiente manera: $D(f)=O(R_{2}(f)^{3})$ .​ (Nisan también mostró que $D(f)=O(R_{1}(f)^{2})$). Se conoce una desigualdad más estrecha entre los modelos Monte Carlo y Las Vegas: $R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))$ .​ Esta relación es óptima módulo factores polilogarítmicos.​ En cuanto a las complejidades del árbol de decisión cuántica, $D(f)=O(Q_{2}(f)^{4})$, y esta cuota es estrecha.​ Midrijanis demostró que $D(f)=O(Q_{0}(f)^{3})$, mejorando una cuota cuártica debida a Beals et al.​

Es importante señalar que estas relaciones polinómicas son válidas solo para funciones booleanas totales . Para funciones Booleanas parciales, que tienen como dominio un subconjunto de $\{0,1\}^{n}$, una separación exponencial entre $Q_{0}(f)$ y $D(f)$ es posible; el primer ejemplo de tal problema fue descubierto por Deutsch y Jozsa .

Conjetura de sensibilidad

Para una función booleana $f:\{0,1\}^{n}\to \{0,1\}$, la sensibilidad de $f$ se define como la máxima sensibilidad de $f$ en cualquier $x$, donde la sensibilidad de $f$ en $x$ es el número de cambios de un solo bit en $x$ que cambia el valor de $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 $x$ .

La conjetura de sensibilidad dice que la sensibilidad está polinomialmente relacionada con la complejidad de consulta; es decir, existen exponentes $c,c'$ tales que, para toda $f$, $D(f)=O(s(f)^{c})$ y $s(f)=O(D(f)^{c'})$ . Uno puede mostrar a través de un argumento simple que $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 $f$, denotado $bs(f)$, se define como la máxima sensibilidad de bloque de $f$ en cualquiera $x$ . La sensibilidad de bloque de $f$ en $x$ es el número máximo $t$ de subconjuntos disjuntos $S_{1},\ldots ,S_{t}\subset [n]$ tal que, para cualquiera de los subconjuntos $S_{i}$, volteando los pedacitos de $x$ correspondiente a $S_{i}$ cambia el valor de $f(x)$ .​

Dado que la sensibilidad de bloque toma su máximo valor en más opciones de subconjuntos, $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 $bs(f)\leq D(f)=O(bs(f)^{4})$ .​ Por lo tanto, uno podría reformular la conjetura de la sensibilidad mostrando que, para algunos $c$, $bs(f)=O(s(f)^{c})$ . En 1992, Nisan y Szegedy conjeturaron que $c=2$ es suficiente​ 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.​

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 $bs(f)=O(s(f)^{4})$ .​ 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.​​

Resumen de resultados conocidos

 

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

	$D$	$R_{0}$	$R_{2}$	$C$	$RC$	$bs$	$s$	$Q_{0}$	$\deg$	$Q$	${\widetilde {\deg }}$
$D$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
$R_{0}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
$R$	1	1		2	2, 3	2, 3	3, 6	1.5, 3	2, 3	3, 4	4
$C$	1	1	1, 2		2	2	2.22, 5	1.15, 3	1.63, 3	2, 4	2, 4
$RC$	1	1	1	1		1.5, 2	2, 4	1.15, 2	1.63, 2	2	2
$bs$	1	1	1	1	1		2, 4	1.15, 2	1.63, 2	2	2
$s$	1	1	1	1	1	1		1.15, 2	1.63, 2	2	2
$Q_{0}$	1	1.33, 2	1.33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
$\deg$	1	1.33, 2	1.33, 2	2	2	2	2	1		2	2
$Q$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
${\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 $A$ -ésima fila y $B$ -ésima columna denota las cuotas en el exponente $c$, que es el ínfimo de toda $k$ que satisface $A(f)=O(B(f)^{k})$ para todas las funciones booleanas $f$ . Por ejemplo, la entrada en la D-ésima fila y la s-ésima columna es "3, 6", por lo que $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ para toda $f$, y existe una función $g$ tal que $D(g)=\Omega (\operatorname {s} (g)^{3-o(1)})$ .

Véase también

• Sorteo por comparación
• Árbol de decisión
• Conjetura de Aanderaa-Karp-Rosenberg
• Árbol de expansión mínima#Árboles de decisión

Referencias

Encuestas

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

• Datos: Q5249246