, con dos resultados (suponiendo que ningún par de elementos sean iguales):
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.
Suponiendo que los elementos a clasificar son todos distintos y comparables, esto se puede reformular como una pregunta de sí o no: ¿es
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.
Se puede mostrar que los ordenamientos de comparación deben usar
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,
Como resultado, esto también funciona para árboles de decisión aleatorios.
Por ejemplo, considera la tarea de usar solo comparaciones para encontrar el número más pequeño entre
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.
(Los algoritmos en este modelo solo pueden depender del signo de la salida. )
Por su definición, los árboles de decisión lineales solo pueden especificar funciones
cuyas fibras se pueden construir tomando uniones e intersecciones de semiespacios.
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[3] y Reingold,[4] se utilizan a menudo para demostrar cuotas inferiores en geometría computacional .
[6] Esto fue mostrado por primera vez para los modelos de decisión lineal por Dobkin y Lipton.
es la profundidad más pequeña entre todos los árboles de decisión deterministas que calculan
Otra definición equivalente lo construye como una distribución sobre árboles de decisión deterministas.
También hay una versión de error acotado unilateral que se denota por
Se conoce una desigualdad más estrecha entre los modelos Monte Carlo y Las Vegas:
[15] En cuanto a las complejidades del árbol de decisión cuántica,
, mejorando una cuota cuártica debida a Beals et al.
[9] 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
es posible; el primer ejemplo de tal problema fue descubierto por Deutsch y Jozsa .
Uno puede mostrar a través de un argumento simple que
, por lo que la conjetura se ocupa específicamente de encontrar una cuota inferior para la sensibilidad.
[13] Por lo tanto, uno podría reformular la conjetura de la sensibilidad mostrando que, para algunos
Huang prueba esto en dos páginas, mientras que el progreso previo hacia la conjetura de sensibilidad había sido limitado.
Por ejemplo, la entrada en la D-ésima fila y la s-ésima columna es "3, 6", por lo que