Modelo de árbol de decisión

En la teoría de la complejidad computacional , el modelo de árbol de decisión es el modelo de computación en el que un algoritmo puede considerarse un árbol de decisión , es decir, una secuencia de consultas o pruebas que se realizan de forma adaptativa, de modo que el resultado de las pruebas anteriores puede influir en las pruebas que se realizan a continuación.

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

Los modelos de árbol de decisión son fundamentales para establecer límites inferiores a la complejidad de ciertas clases de problemas y algoritmos computacionales. Se han introducido diversas variantes de modelos de árbol de decisión, dependiendo del modelo computacional y del tipo de consulta que se permite realizar a los algoritmos.

Por ejemplo, se utiliza un argumento de árbol de decisión para demostrar que una comparación de algún tipo${\displaystyle n}$Los artículos deben cumplir${\displaystyle n\log(n)}$comparaciones. Para las ordenaciones por comparación, una consulta es una comparación de dos elementos.${\displaystyle a,b}$, con dos resultados (suponiendo que ningún elemento sea igual): o bien${\displaystyle a<b}$o${\displaystyle a>b}$En este modelo, las ordenaciones por comparación pueden expresarse como árboles de decisión, ya que dichos algoritmos de ordenación solo realizan este tipo de consultas.

Los árboles de decisión se emplean a menudo para comprender algoritmos de ordenación y otros problemas similares; esto fue realizado por primera vez por Ford y Johnson . ^{[ 1 ]}

Por ejemplo, muchos algoritmos de ordenación son de ordenación por comparación , lo que significa que solo obtienen información sobre una secuencia de entrada.${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$mediante comparaciones locales: probar si${\displaystyle x_{i}<x_{j}}$,${\displaystyle x_{i}=x_{j}}$, o${\displaystyle 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${\displaystyle x_{i}>x_{j}}$¿

Estos algoritmos pueden modelarse 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, la salida corresponde a una permutación.${\displaystyle \pi }$que describe cómo se desordenó la secuencia de entrada a partir de la lista de elementos completamente ordenados. (La inversa de esta permutación,${\displaystyle \pi ^{-1}}$(reordena la secuencia de entrada.)

Se puede demostrar que las clasificaciones por comparación deben utilizar${\displaystyle \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${\displaystyle n}$elementos; de lo contrario, el algoritmo fallaría para esa permutación en particular como entrada. Por lo tanto, su árbol de decisión correspondiente debe tener al menos tantas hojas como permutaciones:${\displaystyle n!}$hojas. Cualquier árbol binario con al menos${\displaystyle n!}$Las hojas tienen profundidad al menos${\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}$Por lo tanto, este es un límite inferior para el tiempo de ejecución de un algoritmo de ordenación por comparación . En este caso, la existencia de numerosos algoritmos de ordenación por comparación con esta complejidad temporal, como mergesort y heapsort , demuestra que el límite es ajustado. ^{[ 2 ] : 91}

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

Otros límites inferiores de árboles de decisión utilizan el hecho de que la consulta es una comparación. Por ejemplo, considere la tarea de usar solo comparaciones para encontrar el número más pequeño entre${\displaystyle 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" (compararse con uno mayor) en al menos una comparación. Por lo tanto, se necesitan al menos${\displaystyle n-1}$comparaciones para encontrar el mínimo. (El argumento de la teoría de la información aquí solo da una cota inferior de${\displaystyle \log(n)}$.) Un argumento similar funciona para cotas inferiores generales para el cálculo de estadísticas de orden . ^{[ 2 ] : 214}

Los árboles de decisión lineales generalizan los árboles de decisión de comparación anteriores para calcular funciones que toman vectores reales.${\displaystyle x\in \mathbb {R} ^{n}}$como entrada. Las pruebas en los árboles de decisión lineales son funciones lineales: para una elección particular de números reales${\displaystyle a_{0},\dots ,a_{n}}$, muestra el signo de${\displaystyle 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${\displaystyle x_{i}}$y${\displaystyle x_{j}}$corresponde a la función lineal${\displaystyle x_{i}-x_{j}}$Por definición, los árboles de decisión lineales solo pueden especificar funciones.${\displaystyle f}$cuyas fibras pueden construirse 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${\displaystyle d}$Geométricamente, el espacio se divide en conjuntos semialgebraicos (una generalización de un hiperplano ).

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

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

De las definiciones se deduce inmediatamente que para todos${\displaystyle n}$Funciones booleanas de -bit${\displaystyle f}$,${\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}$, y${\displaystyle Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n}$Encontrar los mejores límites superiores en la dirección inversa es un objetivo principal en el campo de la complejidad de las consultas.

Todos estos tipos de complejidad de consulta están relacionados polinómicamente. Blum e Impagliazzo, ^{[ 10 ]} Hartmanis y Hemachandra, ^{[ 11 ]} y Tardos ^{[ 12 ]} descubrieron independientemente que${\displaystyle 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 :${\displaystyle D(f)=O(R_{2}(f)^{3})}$. ^{[ 13 ]} (Nisan también demostró que${\displaystyle D(f)=O(R_{1}(f)^{2})}$.) Se sabe que existe una relación más estrecha entre los modelos de Montecarlo y Las Vegas:${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$. ^{[ 14 ]} Esta relación es óptima salvo factores polilogarítmicos. ^{[ 15 ]} En cuanto a las complejidades de los árboles de decisión cuánticos,${\displaystyle D(f)=O(Q_{2}(f)^{4})}$y este límite es estrecho. ^{[ 16 ] [ 15 ]} Midrijanis demostró que${\displaystyle D(f)=O(Q_{0}(f)^{3})}$, ^{[ 17 ] [ 18 ]} mejorando una cota cuártica debida a Beals et al. ^{[ 9 ]}

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

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