Modelo de árbol de decisión

Modelo de complejidad computacional

Modelo de árbol de decisiones

En la teoría de la complejidad computacional , el modelo de árbol de decisión es el modelo de cálculo 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, por lo que el resultado de las pruebas anteriores puede influir en las pruebas que se realizan a continuación.

Por lo general, estas pruebas tienen una pequeña cantidad de resultados (como una pregunta de sí o no ) y se pueden realizar rápidamente (por ejemplo, con un costo 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 del árbol de decisión o complejidad de la consulta .

Los modelos de árboles de decisión son fundamentales para establecer límites inferiores para la complejidad de ciertas clases de problemas computacionales y algoritmos. 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, se utiliza un argumento de árbol de decisión para mostrar que una ordenación de comparación de elementos debe realizar comparaciones. Para las ordenaciones de comparación, una consulta es una comparación de dos elementos , con dos resultados (suponiendo que ningún elemento es igual): o bien . Las ordenaciones de comparación se pueden expresar como árboles de decisión en este modelo, ya que dichos algoritmos de ordenación solo realizan este tipo de consultas. ${\displaystyle n}$ ${\displaystyle n\log(n)}$ ${\displaystyle a,b}$ ${\displaystyle a<b}$ ${\displaystyle a>b}$

Árboles de comparación y límites inferiores para la ordenación

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

Por ejemplo, muchos algoritmos de ordenamiento son ordenamientos por comparación , lo que significa que solo obtienen información sobre una secuencia de entrada a través de comparaciones locales: probando si , o . Suponiendo que los elementos que se van a ordenar son todos distintos y comparables, esto se puede reformular como una pregunta de sí o no: ¿es ? ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ ${\displaystyle x_{i}<x_{j}}$ ${\displaystyle x_{i}=x_{j}}$ ${\displaystyle x_{i}>x_{j}}$ ${\displaystyle 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, la salida corresponde a una permutación que describe cómo se mezcló la secuencia de entrada a partir de la lista de elementos completamente ordenada. (La inversa de esta permutación, , reordena la secuencia de entrada). ${\displaystyle \pi }$ ${\displaystyle \pi ^{-1}}$

Se puede demostrar que los ordenamientos por comparación deben utilizar comparaciones mediante un argumento simple: para que un algoritmo sea correcto, debe ser capaz de generar como salida cada permutación posible de elementos; de lo contrario, el algoritmo fallaría para esa permutación particular como entrada. Por lo tanto, su árbol de decisión correspondiente debe tener al menos tantas hojas como permutaciones: hojas. Cualquier árbol binario con al menos hojas tiene una profundidad de al menos , 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 mergesort y heapsort , demuestra que el límite es estricto. ^{[2] : 91} ${\displaystyle \Omega (n\log(n))}$ ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle n!}$ ${\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}$

Este argumento no utiliza nada sobre el tipo de consulta, por lo que, de hecho, demuestra un límite inferior para cualquier algoritmo de ordenamiento 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 de que un algoritmo de ordenamiento correcto debe aprender al menos bits de información sobre la secuencia de entrada. Como resultado, esto también funciona para árboles de decisión aleatorios. ${\displaystyle \log _{2}(n!)}$

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

Árboles de decisión lineales y algebraicos

Los árboles de decisión lineales generalizan los árboles de decisión de comparación anteriores para calcular funciones que toman vectores reales como entrada. Las pruebas en árboles de decisión lineales son funciones lineales: para una elección particular de números reales , se obtiene como salida el signo de . (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 y corresponde a la función lineal . Según su definición, los árboles de decisión lineal solo pueden especificar funciones cuyas fibras se pueden construir tomando uniones e intersecciones de semiespacios. ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle a_{0},\dots ,a_{n}}$ ${\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}-x_{j}}$ ${\displaystyle f}$

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 . Geométricamente, el espacio se divide en conjuntos semialgebraicos (una generalización del hiperplano). ${\displaystyle d}$

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

Complejidades del árbol de decisión booleano

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

Árbol de decisión determinista

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

Árbol de decisión aleatorio

Una forma de definir un árbol de decisión aleatorio es agregar nodos adicionales al árbol, cada uno controlado por una probabilidad . Otra definición equivalente es definirlo 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 profundidad más grande entre todos los árboles en apoyo de la distribución subyacente. se define como la complejidad del árbol de decisión aleatorio de profundidad más baja cuyo resultado es con probabilidad al menos para todos (es decir, con error bilateral acotado). ${\displaystyle p_{i}}$ ${\displaystyle R_{2}(f)}$ ${\displaystyle f(x)}$ ${\displaystyle 2/3}$ ${\displaystyle x\in \{0,1\}^{n}}$

${\displaystyle R_{2}(f)}$Se conoce como complejidad de árbol de decisión aleatorizado de Monte Carlo , porque se permite que el resultado sea incorrecto con un error bilateral acotado. La complejidad de árbol de decisión de Las Vegas mide la profundidad esperada de un árbol de decisión que debe ser correcto (es decir, que tenga cero errores). También existe una versión unilateral con error acotado que se denota por . ${\displaystyle R_{0}(f)}$ ${\displaystyle 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 analizar para evaluar la función con certeza.

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

Árbol de decisión cuántico

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

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

Beals et al. establecieron que y . ^[9] ${\displaystyle Q_{0}(f)\geq \deg(f)/2}$ ${\displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}$

Relaciones entre las medidas de complejidad de funciones booleanas

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

Todos estos tipos de complejidad de consulta están relacionados polinomialmente. Blum e Impagliazzo, ^[10] Hartmanis y Hemachandra, ^[11] y Tardos ^[12] descubrieron de forma independiente que . Noam Nisan descubrió que la complejidad del árbol de decisión aleatorio de Monte Carlo también está relacionada polinomialmente con la complejidad del árbol de decisión determinista: . ^[13] (Nisan también demostró que .) Se conoce una relación más estrecha entre los modelos de Monte Carlo y Las Vegas: . ^[14] Esta relación es óptima hasta factores polilogarítmicos. ^[15] En cuanto a las complejidades del árbol de decisión cuántico, , y este límite es estrecho. ^{[16] [15]} Midrijanis demostró que , ^{[17] [18]} mejorando un límite cuártico debido a Beals et al. ^[9] ${\displaystyle D(f)\leq R_{0}(f)^{2}}$ ${\displaystyle D(f)=O(R_{2}(f)^{3})}$ ${\displaystyle D(f)=O(R_{1}(f)^{2})}$ ${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$ ${\displaystyle D(f)=O(Q_{2}(f)^{4})}$ ${\displaystyle D(f)=O(Q_{0}(f)^{3})}$

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

Conjetura de sensibilidad

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

La conjetura de sensibilidad es la conjetura de que la sensibilidad está relacionada polinómicamente con la complejidad de la consulta; es decir, existe un exponente tal que, para todos , y . Se puede demostrar mediante un argumento simple que , por lo que la conjetura se ocupa específicamente de encontrar un límite 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 generalmente se expresa como la cuestión de relacionar la sensibilidad con la sensibilidad de bloque. ${\displaystyle c,c'}$ ${\displaystyle f}$ ${\displaystyle D(f)=O(s(f)^{c})}$ ${\displaystyle s(f)=O(D(f)^{c'})}$ ${\displaystyle s(f)\leq D(f)}$

La sensibilidad de bloque de , denotada , se define como la sensibilidad de bloque máxima de todos los . La sensibilidad de bloque de en es el número máximo de subconjuntos disjuntos tales que, para cualquiera de los subconjuntos , al invertir los bits de correspondientes a cambia el valor de . ^[13] ${\displaystyle f}$ ${\displaystyle bs(f)}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle t}$ ${\displaystyle S_{1},\ldots ,S_{t}\subset [n]}$ ${\displaystyle S_{i}}$ ${\displaystyle x}$ ${\displaystyle S_{i}}$ ${\displaystyle f(x)}$

En 2019, Hao Huang demostró la conjetura de sensibilidad, mostrando que . ^{[19] [20]} ${\displaystyle bs(f)=O(s(f)^{4})}$

Véase también

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

Referencias

1. Ford, Lester R. Jr.; Johnson, Selmer M. (1 de mayo de 1959). "Un problema de torneo". The American Mathematical Monthly . 66 (5): 387–389. doi :10.1080/00029890.1959.11989306. ISSN  0002-9890.
2. Introducción a los algoritmos. Cormen, Thomas H. (Tercera edición). Cambridge, Mass.: MIT Press. 2009. ISBN 978-0-262-27083-0.OCLC 676697295  .{{cite book}}: CS1 maint: others (link)
3. Rabin, Michael O. (1972-12-01). "Demostración de positividad simultánea de formas lineales". Journal of Computer and System Sciences . 6 (6): 639–650. doi : 10.1016/S0022-0000(72)80034-5 . ISSN  0022-0000.
4. Reingold, Edward M. (1972-10-01). "Sobre la optimalidad de algunos algoritmos de conjuntos". Revista de la ACM . 19 (4): 649–659. doi : 10.1145/321724.321730 . ISSN  0004-5411. S2CID  18605212.
5. Preparata, Franco P. (1985). Geometría computacional: una introducción. Shamos, Michael Ian. Nueva York: Springer-Verlag. ISBN 0-387-96131-3.OCLC 11970840  .
6. Ben-Or, Michael (1983-12-01). "Límites inferiores para árboles de cálculo algebraico". Actas del decimoquinto simposio anual de la ACM sobre teoría de la computación - STOC '83 . STOC '83. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 80–86. doi : 10.1145/800061.808735 . ISBN 978-0-89791-099-6.S2CID1499957  .​
7. Dobkin, David; Lipton, Richard J. (1 de junio de 1976). "Problemas de búsqueda multidimensional". Revista SIAM de informática . 5 (2): 181–186. doi :10.1137/0205015. ISSN  0097-5397.
8. Michael Steele, J; Yao, Andrew C (1 de marzo de 1982). "Límites inferiores para árboles de decisión algebraicos". Journal of Algorithms . 3 (1): 1–8. doi :10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
9. Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "Límites inferiores cuánticos mediante polinomios". Revista de la ACM . 48 (4): 778–797. arXiv : quant-ph/9802049 . doi :10.1145/502090.502097. S2CID  1078168.
10. Blum, M.; Impagliazzo, R. (1987). "Oráculos genéricos y clases de oráculos". Actas del 18.º IEEE FOCS . págs. 118–126.
11. Hartmanis, J.; Hemachandra, L. (1987), "Funciones unidireccionales, robustez y no isomorfismo de conjuntos NP-completos", Informe técnico DCS TR86-796, Universidad de Cornell
12. Tardos, G. (1989). "Complejidad de consultas, o ¿por qué es difícil separar NP ^A  ∩  coNP ^A de P ^A mediante oráculos aleatorios A ?". Combinatorica . 9 (4): 385–392. doi :10.1007/BF02125350. S2CID  45372592.
13. Nisan, N. (1989). "CREW PRAMs y árboles de decisión". Actas del 21.º ACM STOC . págs. 327–335.
14. Kulkarni, R. y Tal, A. Sobre la sensibilidad de bloques fraccionarios. Coloquio electrónico sobre complejidad computacional (ECCC). Vol. 20. 2013.
15. Ambainis, Andris; Balodis, Kaspars; Belovs, Aleksandrs; Lee, Troya; Santa, Miklos; Smotrovs, Juris (4 de septiembre de 2017). "Separaciones en la complejidad de consultas basadas en funciones de puntero". Revista de la ACM . 64 (5): 32:1–32:24. arXiv : 1506.04719 . doi :10.1145/3106234. ISSN  0004-5411. S2CID  10214557.
16. Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (23 de octubre de 2020). "Grado vs. Grado aproximado e implicaciones cuánticas del teorema de sensibilidad de Huang". arXiv : 2010.12629 [quant-ph].
17. Midrijanis, Gatis (2004), "Complejidad de consulta cuántica exacta para funciones booleanas totales", arXiv : quant-ph/0403168
18. Midrijanis, Gatis (2005), "Sobre las complejidades de las consultas aleatorias y cuánticas", arXiv : quant-ph/0501142
19. Huang, Hao (2019). "Subgrafos inducidos de hipercubos y una prueba de la conjetura de sensibilidad". Anales de Matemáticas . 190 (3): 949–955. arXiv : 1907.00847 . doi :10.4007/annals.2019.190.3.6. ISSN  0003-486X. JSTOR  10.4007/annals.2019.190.3.6. S2CID  195767594.
20. Klarreich, Erica. "Conjetura de hace décadas en informática resuelta en dos páginas". Quanta Magazine . Consultado el 26 de julio de 2019 .

Encuestas

• Buhrman, Harry; de Wolf, Ronald (2002), "Medidas de complejidad y complejidad de árboles de decisión: una encuesta" (PDF) , Theoretical Computer Science , 288 (1): 21–43, doi : 10.1016/S0304-3975(01)00144-X